AlgoProblem►Basic

求最长等差数列

最长等差数列

最长连续子序列 longest consecutive sequence 问题的升级版
，大家一定很熟LCS问题的求解方法，甚至他的单调队列优化版本（栈优化）。

这里我们将讨论其变形版：给出一系列的随机的整数数列。要求在$O(n^2)$的时间复杂度内求解出一个最长的子序列并且为等差数列。

这里需要注意的是题目描述里并没有说明是输出等差数列的长度还是等差数列本身。

这其实也是一个被别人研究过的问题，我这里只是给出这一问题的简单总结

一个观点

方法一

一个比较简单粗暴的方法就是枚举每两个数列项，在哈希表中维护[num, d]状态的个数，记录所有可能出现的等差数列。

伪代码如下：

1
2
3
4
for i in range(n-1, 0)
	for j in range(i+1, n-1)
		d = num[j] - num[i] #数列差
		HASH[num[i], d] = HASH[num[j], d] + 1

显然下面的描述也是等效的：

1
2
3
4
for i in range(0, n-1)
	for j in range(i+1, n-1)
		d = num[j] - num[i] #数列差
		HASH[num[j], d] = HASH[num[i], d] + 1

C++实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main(int argc, char const* argv[]) {
    unordered_map<pair<int, int>, int> HASH1;
    int N;
    int d;
    cin >> N;
    int num[N];
    for (int i = 0; i < N; i++) {
        cin >> num[i];
    }

    for (int i = N-1; i >= 0; i--) {
        for (int j = i+1; j < N; j++) {
            d = num[j] - num[i];
            HASH1[mp(num[i], d)] = HASH1[mp(num[j], d)] + 1;
        }
    }

    int MAX = INT_MIN;
    for (auto &a : HASH1) {
        DBN(a.second);
        if (MAX < a.second) {
            MAX = a.second;
        }
    }
    printf("%d\n", MAX+1);
    return 0;
}

当然如果是自己编写的哈希表效率会更好些。

方法二

这里给出另一个dp的解法，用dp(i,j)表示第i项与第j项构成的等差数列的数量。

C++实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define MAX_N 10001

int main(int argc, char const* argv[]) {
    int N; int d; int pre;
    unordered_map<int, int> eleMap;
    int dp[MAX_N][MAX_N];
    cin >> N;
    int num[N];
    for (int i = 0; i < N; i++) {
        cin >> num[i];
        eleMap[num[i]] = i;   // 逆映射
    }

    int MAX = INT_MIN;
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            d = num[j] - num[i];
            pre = num[i] - d;
            auto it = eleMap.find(pre);
            if (it != eleMap.end()) {
                dp[i][j] = dp[it->second][i] + 1;
            }
            else {
                dp[i][j] = 2;
            }
            if (dp[i][j] > MAX) {
                MAX = dp[i][j];
            }
        }
    }
    printf("%d\n", MAX);

    return 0;
}

另一个观点

如果我们把问题条件改一下，输出不是子序列，而是一个子集，这个自己可以构成等差数列，那么这个问题怎么求解？其实我们只要先排序就好了。