LeetCode 1027: Longest Arithmetic Subsequence (DP on Ending Index and Difference)
LeetCode 1027Dynamic ProgrammingHash MapToday we solve LeetCode 1027 - Longest Arithmetic Subsequence.
Source: https://leetcode.com/problems/longest-arithmetic-subsequence/
English
Problem Summary
Given an integer array nums, return the length of the longest arithmetic subsequence. A subsequence keeps order but can skip elements, and arithmetic means adjacent values have the same difference.
Key Insight
Use DP by (ending index i, common difference d). Let dp[i][d] be the best length of an arithmetic subsequence ending at i with difference d. For every pair j < i, we can extend the chain ending at j with the same d = nums[i] - nums[j].
Algorithm
- Create an array of hash maps dp, one map per index.
- For each i, iterate all j < i.
- Compute d = nums[i] - nums[j].
- Transition: dp[i][d] = max(dp[i][d], dp[j].get(d, 1) + 1).
- Track global maximum.
Complexity Analysis
Time: O(n^2).
Space: O(n^2) in the worst case (many distinct differences).
Common Pitfalls
- Initial base length should behave like 1 before adding current element, so pair length becomes 2.
- Overwriting dp[i][d] without max can lose a longer chain.
- Using fixed diff range assumptions can fail for general integer values.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int longestArithSeqLength(int[] nums) {
int n = nums.length;
@SuppressWarnings("unchecked")
java.util.HashMap<Integer, Integer>[] dp = new java.util.HashMap[n];
for (int i = 0; i < n; i++) dp[i] = new java.util.HashMap<>();
int ans = 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int d = nums[i] - nums[j];
int cand = dp[j].getOrDefault(d, 1) + 1;
int best = Math.max(dp[i].getOrDefault(d, 0), cand);
dp[i].put(d, best);
ans = Math.max(ans, best);
}
}
return ans;
}
}func longestArithSeqLength(nums []int) int {
n := len(nums)
dp := make([]map[int]int, n)
for i := 0; i < n; i++ {
dp[i] = make(map[int]int)
}
ans := 2
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
d := nums[i] - nums[j]
prev, ok := dp[j][d]
if !ok {
prev = 1
}
cand := prev + 1
if cand > dp[i][d] {
dp[i][d] = cand
}
if dp[i][d] > ans {
ans = dp[i][d]
}
}
}
return ans
}class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
int n = nums.size();
vector<unordered_map<int, int>> dp(n);
int ans = 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int d = nums[i] - nums[j];
int prev = dp[j].count(d) ? dp[j][d] : 1;
int cand = prev + 1;
dp[i][d] = max(dp[i][d], cand);
ans = max(ans, dp[i][d]);
}
}
return ans;
}
};class Solution:
def longestArithSeqLength(self, nums: List[int]) -> int:
n = len(nums)
dp = [dict() for _ in range(n)]
ans = 2
for i in range(n):
for j in range(i):
d = nums[i] - nums[j]
cand = dp[j].get(d, 1) + 1
dp[i][d] = max(dp[i].get(d, 0), cand)
ans = max(ans, dp[i][d])
return ans/**
* @param {number[]} nums
* @return {number}
*/
var longestArithSeqLength = function(nums) {
const n = nums.length;
const dp = Array.from({ length: n }, () => new Map());
let ans = 2;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
const d = nums[i] - nums[j];
const prev = dp[j].has(d) ? dp[j].get(d) : 1;
const cand = prev + 1;
const best = Math.max(dp[i].get(d) || 0, cand);
dp[i].set(d, best);
ans = Math.max(ans, best);
}
}
return ans;
};中文
题目概述
给定整数数组 nums，返回最长等差子序列的长度。子序列要求保持原顺序（可跳过元素），等差表示相邻元素差值相同。
核心思路
做二维状态 DP，但用哈希表压缩差值维度。定义 dp[i][d] 表示以 i 结尾、公差为 d 的最长长度。枚举所有 j < i，令 d = nums[i] - nums[j]，把 j 的链延长到 i。
算法步骤
- 准备长度为 n 的哈希表数组 dp。
- 枚举每个 i，再枚举 j = 0..i-1。
- 计算差值 d = nums[i] - nums[j]。
- 转移：dp[i][d] = max(dp[i][d], dp[j].get(d, 1) + 1)。
- 维护全局最大值。
复杂度分析
时间复杂度：O(n^2)。
空间复杂度：最坏 O(n^2)（差值种类很多时）。
常见陷阱
- 基础长度要按“已有 1 个，再接当前元素”处理，否则长度会少算。
- 未取 max 直接覆盖，会丢失更优状态。
- 误用固定公差范围，导致对一般整数输入不稳健。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int longestArithSeqLength(int[] nums) {
int n = nums.length;
@SuppressWarnings("unchecked")
java.util.HashMap<Integer, Integer>[] dp = new java.util.HashMap[n];
for (int i = 0; i < n; i++) dp[i] = new java.util.HashMap<>();
int ans = 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int d = nums[i] - nums[j];
int cand = dp[j].getOrDefault(d, 1) + 1;
int best = Math.max(dp[i].getOrDefault(d, 0), cand);
dp[i].put(d, best);
ans = Math.max(ans, best);
}
}
return ans;
}
}func longestArithSeqLength(nums []int) int {
n := len(nums)
dp := make([]map[int]int, n)
for i := 0; i < n; i++ {
dp[i] = make(map[int]int)
}
ans := 2
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
d := nums[i] - nums[j]
prev, ok := dp[j][d]
if !ok {
prev = 1
}
cand := prev + 1
if cand > dp[i][d] {
dp[i][d] = cand
}
if dp[i][d] > ans {
ans = dp[i][d]
}
}
}
return ans
}class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
int n = nums.size();
vector<unordered_map<int, int>> dp(n);
int ans = 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int d = nums[i] - nums[j];
int prev = dp[j].count(d) ? dp[j][d] : 1;
int cand = prev + 1;
dp[i][d] = max(dp[i][d], cand);
ans = max(ans, dp[i][d]);
}
}
return ans;
}
};class Solution:
def longestArithSeqLength(self, nums: List[int]) -> int:
n = len(nums)
dp = [dict() for _ in range(n)]
ans = 2
for i in range(n):
for j in range(i):
d = nums[i] - nums[j]
cand = dp[j].get(d, 1) + 1
dp[i][d] = max(dp[i].get(d, 0), cand)
ans = max(ans, dp[i][d])
return ans/**
* @param {number[]} nums
* @return {number}
*/
var longestArithSeqLength = function(nums) {
const n = nums.length;
const dp = Array.from({ length: n }, () => new Map());
let ans = 2;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
const d = nums[i] - nums[j];
const prev = dp[j].has(d) ? dp[j].get(d) : 1;
const cand = prev + 1;
const best = Math.max(dp[i].get(d) || 0, cand);
dp[i].set(d, best);
ans = Math.max(ans, best);
}
}
return ans;
};
Comments