思路分析:
-
使用动态规划的思想,定义二维数组
dp
,其中dp[i][j]
表示以nums[i]
为结尾,公差为(j-1000)
的等差数列长度。为了适应负数的情况,将公差的范围设为[-1000, 1000],并且加上1000作为数组索引。 -
初始化
result
为0,用于存储最终的最长等差数列长度。 -
使用两层循环遍历数组,对于每一对(i, j),计算它们的差值
diff = nums[j] - nums[i] + 1000
。 -
更新
dp[j][diff]
为dp[i][diff] + 1
,表示当前等差数列的长度比前一个等差数列长度多1。 -
在每次更新
dp[j][diff]
时,都更新一下result
,取当前长度和之前的最大长度的较大值。 -
最终返回
result
作为结果,表示整个数组中最长的等差数列长度。
class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
// 获取数组长度
int n = nums.size();
// 创建一个二维动态规划数组,dp[i][j]表示以nums[i]为结尾,公差为(j-1000)的等差数列长度
// 为了适应负数的情况,将公差的范围设为[-1000, 1000],并且加上1000作为数组索引
vector<vector<int>> dp(n, vector<int>(2002, 1));
// 用于存储最终结果
int result = 0;
// 遍历数组,计算dp数组的值
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// 计算当前等差数列的公差
int diff = nums[j] - nums[i] + 1000;
// 更新dp数组
dp[j][diff] = dp[i][diff] + 1;
// 更新最终结果
result = max(result, dp[j][diff]);
}
}
// 返回最终结果
return result;
}
};