Pattern Guide
Arithmetic Progression DP
"Count/find longest AP subsequences. State = (last, diff). Key: hash by difference."
Arithmetic progression DP finds longest/count AP subsequences. State: dp[i][d] = length of longest AP ending at index i with common difference d. Transition: for each j < i, dp[i][d] = dp[j][d-that is wrong... dp[i][(arr[i]-arr[j])] = dp[j][(arr[i]-arr[j])] + 1. Use hashmaps for the difference dimension. Key: O(n²) with hashmaps, or O(n² log n) if sorted.
Problems you can solve with this pattern
4 problems · click any to start solving
// Longest arithmetic subsequence
function longestArithSeqLength(nums) {
const n = nums.length;
const dp = Array.from({length: n}, () => new Map());
let ans = 2;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
const d = nums[i] - nums[j];
const len = (dp[j].get(d) ?? 1) + 1;
dp[i].set(d, Math.max(dp[i].get(d) ?? 2, len));
ans = Math.max(ans, dp[i].get(d));
}
}
return ans;
}
// Count arithmetic slices (subarrays) with at least 3 elements
function countArithSlices(nums) {
const n = nums.length;
let total = 0, cur = 0;
for (let i = 2; i < n; i++) {
if (nums[i] - nums[i-1] === nums[i-1] - nums[i-2]) {
cur++;
total += cur;
} else {
cur = 0;
}
}
return total;
}
// Count arithmetic subsequences (not just subarrays)
function countArithSeqSubseq(nums) {
const MOD = 1e9 + 7;
const n = nums.length;
const dp = Array.from({length: n}, () => new Map());
let total = 0;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
const d = nums[i] - nums[j];
const prevLen = dp[j].get(d) ?? 0;
const newLen = prevLen + 1;
dp[i].set(d, (dp[i].get(d) ?? 0) + newLen);
total += prevLen; // count subsequences of length >= 3
}
}
return total % MOD;
}For longest arithmetic subsequence: dp[i] is a map from difference d to the length of the longest AP ending at arr[i] with difference d. For each i, j < i: d = arr[i] - arr[j]; dp[i][d] = max(dp[i][d], (dp[j][d] ?? 1) + 1). The answer is the maximum value across all dp[i] maps. O(n²) time with hashmaps for differences.
// Longest arithmetic subsequence
function longestArithSeqLength(nums) {
const n = nums.length;
const dp = Array.from({length: n}, () => new Map());
let ans = 2;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
const d = nums[i] - nums[j];
const len = (dp[j].get(d) ?? 1) + 1;
dp[i].set(d, Math.max(dp[i].get(d) ?? 2, len));
ans = Math.max(ans, dp[i].get(d));
}
}
return ans;
}
// Count arithmetic slices (subarrays) with at least 3 elements
function countArithSlices(nums) {
const n = nums.length;
let total = 0, cur = 0;
for (let i = 2; i < n; i++) {
if (nums[i] - nums[i-1] === nums[i-1] - nums[i-2]) {
cur++;
total += cur;
} else {
cur = 0;
}
}
return total;
}
// Count arithmetic subsequences (not just subarrays)
function countArithSeqSubseq(nums) {
const MOD = 1e9 + 7;
const n = nums.length;
const dp = Array.from({length: n}, () => new Map());
let total = 0;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
const d = nums[i] - nums[j];
const prevLen = dp[j].get(d) ?? 0;
const newLen = prevLen + 1;
dp[i].set(d, (dp[i].get(d) ?? 0) + newLen);
total += prevLen; // count subsequences of length >= 3
}
}
return total % MOD;
}- dp[i][d] = AP length ending at index i with difference d
- Transitions: O(n) per index, n indices → O(n²) total
- Space: O(n²) in worst case (all different differences), but often sparse
Subarrays vs subsequences:
- Subarrays: O(n) with running count (simple)
- Subsequences: O(n²) with hashmaps
Fixed difference: O(n) with a single hashmap dp[value] = longest AP ending at this value.
Optimization for counting: dp stores (partial APs of length ≥ 2) that can be extended. When we extend them to length 3, they contribute to the count.