哇,又是一道水题……
还是说数据太水???
老实说我自己写的时候都没什么自信……

特么居然直接A了

题意:
找出最长的等差序列或者等比序列。输出长度。

思路:
本来就是一道水题,但是尝试用着尺取去写。有点不是很自信。

但是尺取并不是最优的,当找到一个元素和已知序列不构成等差或者等比数列的时候,可以直接跳转到那个位置另外开始判断,这样,时间大概会降低一半左右。

注: 只有一个元素的时候最好特判一下

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

int ary[maxn];

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        each(i, n) scanf("%d", ary + i);
        ary[n] = ary[n + 1] = inf;
        int d = ary[1] - ary[0], dj = 1, qj = 1, ans = 1;
        double q = 1.0 * ary[1] / ary[0];
        each(i, n)
        {
            while (ary[dj + 1] == ary[dj] + d && dj < n)
                dj++;
            while (ary[qj + 1] == ary[qj] * q && qj < n)
                qj++;
            ans = max(ans, dj - i + 1);
            ans = max(ans, qj - i + 1);
            if (i + 1 == dj) {
                d = ary[i + 2] - ary[i + 1];
                dj++;
            }
            if (i + 1 == qj) {
                q = 1.0 * ary[i + 2] / ary[i + 1];
                qj++;
            }
        }
        printf("%d\n", n == 1 ? 1 : ans);
    }
    return 0;
}