LC.P1027[最长等差数列]

方法一：动态规划

定义$f[i][j]$表示以$nums[i]$结尾且公差为$j$的等差数列的最大长度。初始时$f[i][j] = 1$，表示每个元素自身都是一个长度为$1$的等差数列。

由于公差可能为负数，且最大差值为 500 ，因此，可以将统一将公差加上 500，这样公差的范围就变成了 $[0 , 1000]$

如果初始时 $f[i][j] = 0$，那么我们需要在最后返回答案时加上 $1$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length, ans = 0;
        int[][] f = new int[n][1001]; // f[i][j]表示以nums[i]结尾且公差为j的等差数列的最大长度
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int d = nums[i] - nums[j] + 500; // 防止负数
                f[i][d] = Math.max(f[i][d], f[j][d] + 1);
                ans = Math.max(ans, f[i][d]);
            }
        }
        return ans + 1;
    }
}
  • 时间复杂度：$O(n \times (n + d))$，$n$为$nums$的长度，$d = max(nums) - min(nums)$
  • 空间复杂度：$O(n \times d)$