1027. 最长等差数列

发表于 分类于 阅读次数： Waline： 本文字数： 909 阅读时长 ≈ 3 分钟

考点

  • 线性DP

思路

1. 问题描述

给定一个长度为 \(n\) 的整数数组 \(\text{nums}\)，需要在保持相对顺序不变的前提下，选取若干元素构成一个等差子序列，并求该等差子序列的最大长度。

等差子序列的定义为： 若序列为 \((a_1, a_2, \dots, a_k)\)，则存在一个固定的公差 \(d\)，使得对所有 \(i\ge 2\) 都有 \[ a_i - a_{i-1} = d \]

2. 关键约束与建模动机

题目中给出的关键约束是：

  • \(0 \le \text{nums}[i] \le 500\)
  • \(n \le 1000\)

由此可以推出：

  • 任意两个元素的差值范围为 \[ -500 \le d \le 500 \]

  • 数值范围较小，可以考虑按数值而非下标进行状态压缩建模

这为一种“按值 DP（Value-based DP）”提供了可能。

3. 状态定义（State Definition）

定义二维动态规划数组： \[ f[v][d] \] 其含义为：

在已经处理过的前缀中，以“数值等于 \(v\)”结尾、公差为 \(d\) 的最长等差子序列长度。

其中：

  • \(v \in [0, 500]\)
  • \(d \in [-500, 500]\)

由于数组下标不能为负数，实际实现时对公差进行偏移： \[ d \;\longrightarrow\; d + \text{offset}, \quad \text{其中 } \text{offset} = 500 \] 因此第二维下标范围为 \([0,1000]\)。

4. 状态转移方程（State Transition）

在遍历数组时，按顺序处理当前元素 \(x\)。

4.1 枚举公差

对所有可能的公差： \[ d \in [-500, 500] \] 假设当前等差序列的最后一个元素是 \(x\)，那么它的前驱元素值应为： \[ \text{pre} = x - d \]

4.2 转移情况分析

情况 1：前驱值不存在（越界）

若： \[ \text{pre} < 0 \quad \text{或} \quad \text{pre} > 500 \] 则不可能存在合法的前驱元素，此时只能将当前元素单独作为序列起点： \[ f[x][d] = 1 \]

情况 2：前驱值合法

若： \[ 0 \le \text{pre} \le 500 \] 则可以在“以 \(\text{pre}\) 结尾、公差为 \(d\)”的最优序列后追加当前元素 \(x\)，状态转移为： \[ f[x][d] = f[\text{pre}][d] + 1 \]

4.3 完整转移公式

综合两种情况，状态转移可写为： \[ f[x][d] = \begin{cases} 1, & \text{若 } x - d \notin [0,500] \\ f[x-d][d] + 1, & \text{否则} \end{cases} \]

5. 初始条件与答案

  • 初始时，所有 \(f[v][d]\) 均为 0；
  • 在转移过程中维护全局最大值：

\[ \text{ans} = \max f[v][d] \]

该最大值即为最长等差子序列的长度。

6. 时间与空间复杂度分析

  • 时间复杂度：

\[ O(n \times 1001) \]

其中 \(n\) 为数组长度，1001 为公差取值范围。

  • 空间复杂度：

\[ O(501 \times 1001) \]

使用定长数组，空间稳定、常数小。

7. AC代码

下面给出该算法的完整实现，并对关键语句进行注释说明。

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
35
36
37
38
class Solution {
public:
    // 将公差 d ∈ [-500, 500] 平移到数组下标 [0, 1000]
    static const int offset = 500;

    int longestArithSeqLength(vector<int>& nums) {
        // f[v][d]：
        // 表示以“数值为 v”结尾、公差为 d-offset 的最长等差子序列长度
        int f[505][1005] = {};

        int mx = 0;   // 记录全局最大长度
        int t, pre, y;

        // 按原数组顺序遍历，保证子序列顺序合法
        for (int x : nums) {
            // 枚举所有可能的公差
            for (int d = -500; d <= 500; ++d) {
                pre = x - d;          // 前驱元素的数值
                y = d + offset;       // 公差映射后的下标

                // 若前驱值越界，则无法接在任何已有序列后
                if (pre < 0 || pre > 500) {
                    // 只能以当前元素单独作为长度为 1 的序列
                    f[x][y] = 1;
                    continue;
                }

                // 否则，在以 pre 结尾、公差为 d 的序列后接上 x
                t = f[pre][y] + 1;
                f[x][y] = t;

                // 更新答案
                mx = max(mx, t);
            }
        }
        return mx;
    }
};