CPP: Longest Progressive Subsequence

Solution for the Longest Progressive Subsequence problem in Cpp

Problem Description

A progressive array in this problem refers to an arithmetic progression, where the difference between every pair of consecutive elements is constant.

Given an integer array, the task is to determine the length of the longest progressive subsequence.

The subsequence does not need to be contiguous, but the relative order of elements must be preserved.

Example

  • Input: A = [9, 2, 4, 7, 1, 10], Output: 3 — because 4 → 7 → 10 has a constant difference of 3.
  • Input: A = [1, 3, 5, 7, 9], Output: 5 — the entire array is a progressive subsequence with difference 2.
  • Input: A = [5, 10, 15, 20, 25], Output: 5 — all elements follow a constant difference of 5.
  • Input: A = [3, 6, 9, 12, 8, 15], Output: 5 — the subsequence 3 → 6 → 9 → 12 → 15 has difference 3.
  • Input: A = [10, 7, 4, 1, -2], Output: 5 — all elements form a progressive subsequence with difference -3.
  • Input: A = [1, 2, 4, 8, 16], Output: 2 — no three elements share the same difference.
  • Input: A = [5], Output: 1 — a single element is a progressive subsequence.
  • Input: A = [7, 7, 7, 7], Output: 4 — all elements form a progressive subsequence with difference 0.

Notes

  • Only integers greater than zero affect the result
  • The smallest possible answer is always at least 1
  • Duplicate values do not change the outcome
  • The solution should scale efficiently for large input sizes

Constraints

  • 1 ≤ N ≤ 2000
  • -10⁶ ≤ A[i] ≤ 10⁶
  • The array may contain negative numbers.
  • The array may be unsorted.
  • The solution must preserve the original order of elements.

Solution

The key idea is to use dynamic programming with hashing.

For each index i, we track all possible arithmetic sequences that end at i using different differences.

We define:

md 
dp[i][d] = length of the longest arithmetic subsequence
           ending at index i with difference d

For every pair of indices (j, i) where j < i:

  • Compute the difference d = A[i] - A[j]
  • If a sequence with difference d already ends at j, extend it
  • Otherwise, start a new sequence of length 2

The maximum value across all states is the final answer.

cpp 
// you can use includes, for example:
// #include <algorithm>
#include <set>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // Implement your solution here

	   int n = A.size();
    if (n <= 2) return n;

    vector<unordered_map<int, int>> dp(n);
    int result = 2;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int diff = A[i] - A[j];

            int length = dp[j].count(diff) ? dp[j][diff] + 1 : 2;
            dp[i][diff] = max(dp[i][diff], length);

            result = max(result, dp[i][diff]);
        }
    }

    return result;
}

Time and Space Complexity

  • Time Complexity: O(N²)
  • Space Complexity: O(N²) in the worst case due to stored differences