Longest Arithmetic Progression

Given an array of integers, return the length of the longest arithmetic subsequence: elements taken in their original order (not necessarily adjacent) whose consecutive differences are all the same. The difference can be positive, negative, or zero.

LeetCode: 1027. Longest Arithmetic Subsequence

Example

Text

[3, 6, 9, 12]               ->  4   (difference 3)
[9, 4, 7, 2, 10]            ->  3   (4, 7, 10)
[20, 1, 15, 3, 10, 5, 8]    ->  4   (20, 15, 10, 5)

Brute force: extend every pair

Any two elements i < j fix the first term and the difference d = nums[j] - nums[i]. Scan the rest of the array, and take each element equal to the next expected term.

Java

public class Main {
    static int longestAp(int[] nums) {
        int n = nums.length;
        int best = Math.min(n, 2);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int d = nums[j] - nums[i];
                int next = nums[j] + d;
                int len = 2;
                for (int k = j + 1; k < n; k++) {
                    if (nums[k] == next) {
                        len++;
                        next += d;
                    }
                }
                best = Math.max(best, len);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestAp(new int[]{3, 6, 9, 12}) + " " + longestAp(new int[]{9, 4, 7, 2, 10}) + " " + longestAp(new int[]{20, 1, 15, 3, 10, 5, 8}));
    }
}

Output

4 3 4

Time: O(n³). Space: O(1).

Taking the first matching element greedily is safe: any later element with the same value could only continue the progression the same way, with fewer elements left after it.

Optimal: DP per index and difference

Let len[j][d] be the length of the longest arithmetic subsequence that ends at index j with difference d. For every earlier i, the element nums[j] extends the progression ending at i with difference d = nums[j] - nums[i]:

Text

len[j][d] = len[i][d] + 1    (or 2, if no progression with difference d ends at i)

Differences can be anything, so each index keeps a HashMap from difference to length. getOrDefault(d, 1) returns the stored length, or 1 when the key is absent (a single element is a progression of length 1). merge(d, extended, Math::max) stores the larger of the old and new value.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static int longestAp(int[] nums) {
        int n = nums.length;
        List<Map<Integer, Integer>> len = new ArrayList<>();
        for (int i = 0; i < n; i++) len.add(new HashMap<>());
        int best = Math.min(n, 2);
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < j; i++) {
                int d = nums[j] - nums[i];
                int extended = len.get(i).getOrDefault(d, 1) + 1;
                int stored = len.get(j).merge(d, extended, Math::max);
                best = Math.max(best, stored);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestAp(new int[]{3, 6, 9, 12}) + " " + longestAp(new int[]{9, 4, 7, 2, 10}) + " " + longestAp(new int[]{20, 1, 15, 3, 10, 5, 8}));
        System.out.println(longestAp(new int[]{5, 5, 5}) + " " + longestAp(new int[]{1}));
    }
}

Output

4 3 4
3 1

Time: O(n²) on average. Space: O(n²) in the worst case, one entry per pair.

With values in a small known range, an int[] indexed by d + offset is faster than a HashMap. nums[j] - nums[i] can overflow int for values near Integer.MIN_VALUE and Integer.MAX_VALUE; use long differences if the input allows such values.

Edge cases

Fewer than two elements: the length of the array.
Equal values: difference 0 is a valid progression.