eoj跑的真的太快了，纯暴力，O（n^3）都给过了。。。。
注意是在数组中选取最多的数组成等差数列，leetcode上有道题是选取子序列组成等差数列，别搞混了。eoj这个可以先把数组排下序，再依次遍历就可以转换成选取子序列的算法了
using namespace std;
int getMax(int a, int b) {
return a > b ? a : b;
}
int main() {
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int n;
cin >> n;
int gap;
vectorarr;
int temp = 0;
int max = 1;
int val;
int tempNum;
for (int i = 0; i < n; i++) {
cin >> val;
arr.push_back(val);
}
sort(arr.begin(),arr.end());
for (int i = 0; i < n; i++) {
for (int k = i + 1; k < n; k++) {
gap = arr[k] - arr[i];
temp = 2;
tempNum = arr[k];
for (int j = k + 1; j < n; j++) {
if (arr[j] - tempNum == gap) {
temp++;
tempNum = arr[j];
}
}
max = getMax(max, temp);
}
}
printf(“case #%d:\n”, i);
cout << max << endl;
eoj跑的真他娘的快啊
此题能够使用枚举法完全是因为数据量过小
O(n^3)的算法在更大的数据量下是完全行不通的
dfs才是此类题目的精髓所在，感兴趣的同学可以细品一下
被暴力标签骗了……直接动手写，后来才发现有问题……然后大改……
虽然说也是暴力没错……
给几组数据自行体会：一、10 1 1 2 2 3 3 4 4 5 5（答案5）； 二、7 1 2 4 5 6 8 9（答案4）
附C代码：
每次做这种题目的时候
我就在想
又到了挑战EOJ速度的时候了…………
不要想任何骚代码，直接暴力！
1.我们第一个枚举的是起始点i
2.枚举差点j，即我们当前选择的差为a[j]-a[i]（i+1≤j≤n）
3.枚举剩余部分k，我们在遍历时便可以查询是否是等差序列，如果差＞我们选择的差，就可以Break
4.求过程中最大长度
时间复杂度O(nlogn+n^3)
include
include
include
include
eoj跑的真的太快了，纯暴力，O（n^3）都给过了。。。。
注意是在数组中选取最多的数组成等差数列，leetcode上有道题是选取子序列组成等差数列，别搞混了。eoj这个可以先把数组排下序，再依次遍历就可以转换成选取子序列的算法了
using namespace std;
int getMax(int a, int b) {
return a > b ? a : b;
}
int main() {
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int n;
cin >> n;
int gap;
vectorarr;
int temp = 0;
int max = 1;
int val;
int tempNum;
for (int i = 0; i < n; i++) {
cin >> val;
arr.push_back(val);
}
sort(arr.begin(),arr.end());
for (int i = 0; i < n; i++) {
for (int k = i + 1; k < n; k++) {
gap = arr[k] - arr[i];
temp = 2;
tempNum = arr[k];
for (int j = k + 1; j < n; j++) {
if (arr[j] - tempNum == gap) {
temp++;
tempNum = arr[j];
}
}
max = getMax(max, temp);
}
}
printf(“case #%d:\n”, i);
cout << max << endl;
}
EOJ太快了~，我都被自己逗笑了