计算一组等差序列的最大长度c++

### 等差序列最大长度的 C++ 实现方法 为了计算等差序列的最大长度，可以采用动态规划的思想，并结合哈希表来记录中间状态。这种方法能够有效地减少时间复杂度，同时保持较高的空间利用率。 #### 动态规划的核心思路 动态规划的关键在于构建一个二维 `dp` 数组或者使用哈希表存储当前状态下可能形成的最长等差子序列长度。对于任意两个下标 `(i, j)` （其中 `i < j`），如果它们之间的差值构成等差关系，则可以通过前序的状态更新当前的结果[^4]。 下面提供两种不同的实现方案： --- #### 方案一：基于两层嵌套循环与哈希表的解法 此方法适用于求解整个数组中的最长等差子序列长度。具体步骤如下： 1. 使用一个二维数组 `dp[n][n]` 来保存每一对元素作为最后两项时对应的最长等差子序列长度。 2. 对于每一个新的元素 `nums[i]` 和后续元素 `nums[j]`，尝试查找是否存在第三个元素使得三者形成等差数列。 3. 如果找到了这样的第三项，则更新相应的 `dp[i][j]` 并维护全局最大值。 下面是完整的代码实现： ```cpp class Solution { public: int longestArithSeqLength(vector<int>& nums) { unordered_map<int, int> hash; // 用于映射数值到其最早出现的位置 hash[nums[0]] = 0; int n = nums.size(); if (n <= 2) return n; vector<vector<int>> dp(n, vector<int>(n, 2)); // 初始化为2，因为最短有效等差至少有两个元素 int ret = 2; for (int i = 1; i < n; ++i) { // 固定倒数第一个数 for (int j = i + 1; j < n; ++j) { // 枚举倒数第二个数 int prevNum = 2 * nums[i] - nums[j]; // 计算期望的前一项 if (hash.find(prevNum) != hash.end()) { // 查找是否有符合条件的前驱节点 dp[i][j] = dp[hash[prevNum]][i] + 1; } ret = max(ret, dp[i][j]); } hash[nums[i]] = i; // 更新当前数字的位置 } return ret; } }; ``` 上述代码的时间复杂度主要由双重循环决定，即 O(N²)，而额外的空间开销来自于大小为 N×N 的 DP 表格以及辅助使用的哈希表[^2]。 --- #### 方案二：单次遍历配合哈希表优化 当只需要考虑特定公差的情况下，可以直接利用单一维度的动态转移方程完成任务。这里介绍一种更加紧凑的方式，仅需线性扫描即可得出答案。 核心思想是通过迭代处理每个数组成员，并将其视为潜在的新起点；与此同时，查询之前已有的键值对以延续已有链条或开辟全新路径。 以下是对应的具体编码实例： ```cpp class Solution { public: int longestSubsequence(vector<int>& arr, int difference) { unordered_map<int, int> dp; // key 是当前元素 value 是以此结束的最长子序列长度 int maxLength = 0; for (int x : arr) { dp[x] = dp[x - difference] + 1; // 若存在前驱则延长链路 否则新建一条长度为1的链路 maxLength = max(maxLength, dp[x]); // 不断刷新最终结果 } return maxLength; } }; ``` 这段程序运行效率更高，因为它只需执行一次顺序访问便能获得目标指标。然而值得注意的是，这种策略只针对固定步幅的情形适用[^1]。 --- ### 总结说明 以上分别展示了两种不同场景下的最优实践案例。前者适合探索未知间距条件下的一般情况，后者则是针对指定增量情形做了专门定制化的改进措施。两者均体现了动态规划的强大功能及其灵活应用价值所在。