阿里建站价格,个人网站设计公司,网站站点连接不安全,wordpress视频模版个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 原题链接点击直接跳转到该题目 目录 1️⃣题目描述2️⃣算法分析3️⃣代码编写 1️⃣题目描述 2️⃣算法分析
整个题目的思路是先求出数组元素之间的最大公约数然后计算最大等差子序列的长度。
那什么时候这个最大等差子序列的长度是最大的呢我们根据等差数列公式来看an a1 (n - 1)d即n (an - a1) / d 1当an最小但是取的是数组中的最大值、a1最大但是取的是数组中的最小值同时d最大即每个元素与第一个元素之间的差值的最大公约数。
3️⃣代码编写
#includeiostream
#includecstdio
#includecstring
#includealgorithmusing namespace std;
const int N 1e5 10;
int arr[N];int gcd(int a,int b)
{return b ? gcd(b,a % b) : a;
}int main()
{int n;cin n;for(int i 0;i n;i) scanf(%d,arr[i]);sort(arr,arr n);int d 0;for(int i 1;i n;i) d gcd(d,arr[i] - arr[0]);if(!d) printf(%d\n,n);else printf(%d\n,(arr[n - 1] - arr[0]) / d 1);return 0;
}最后就顺利通过啦及时复习其中包含的一些小的算法哈比如欧几里得算法~
