Intuition behind Largest Subsequence Problems

In this post, I’ll be explaining the approach to solve this problem:

Given an array A of integers, return the length of the longest arithmetic subsequence in A.

Here’s the problem link on leetcode: https://leetcode.com/problems/longest-arithmetic-sequence/

Using this problem, I’ll be explaining a generic approach to solve all problems of this kind. By this kind, I mean problems where :

you have to find the longest subsequence in an array which follows some pattern.

There’s a standard approach that we follow in these questions. If I’ve to put it in one line, it’d be:

For each index i, you’ve to iterate over all indices j (0 to i-1) and check if you can expand on the result of j

This concept is very similar to Longest Increasing Subsequence problem. For each idx, you check if it can expand on any of it’s previous indices.

Now, let’s introduce a concept here:

`Information(j):` the information needed to store at j to check if we can expand on result(j).

In LIS, Information(j) stores the length of longest increasing subsequence till that element. That’s it.
and we just have to check if A[i] > A[j] to know if we can expand it’s result or not.

In this question, to check if i can expand on result(j), we need to check :
if we take both i and j in an AP, then what would be max length of the AP till i?

Let’s call `diff = A[i]-A[j]`.
So, as per requirement, Result(j) need to store the max length of AP sequence ending at j with `difference = diff`.

Now, this is for only one `i`. We’ll coming over to j for each i (i>j).
So j will store list of numbers, corresponding to each diff.

This is our Information(j) in this case, a list of integers where each integer represents the answer till j for a particular `diff`.

And, we have to store this information at each index. So the DS that we use HashMap<Integer,Integer>[], array of hashmaps.

We start from left and build our structure in a bottom up manner.

Here’s the code for it:

public int longestArithSeqLengthDP(int[] A) {
   // map[i]  stores the Information(i) that we discussed
    HashMap<Integer, Integer>[] map = new HashMap[A.length];
    int ans = 0;
    for (int i = 1; i < A.length; i++) {
	// try to build over result of all the previous indices
      for (int j = 0; j < i; j++) {
        int diff = A[i] - A[j];
        int curAns = 2;
        if (map[j] != null && map[j].containsKey(diff)) {
          curAns = Math.max(curAns, 1 + map[j].get(diff));
        }
        if (map[i] == null) {
          map[i] = new HashMap<>();
        }
        map[i].put(diff, curAns); // storing this for future indices to use.
        ans = Math.max(ans, curAns);
      }
    }
    return ans;
  }

A lot of problems of `finding largest subsequence which follows a particular pattern` can be solved using this approach. You consider all the previous indices to expand their result and decide what all you’ll store at each index.

Here’s another problem which follows this pattern:
https://www.geeksforgeeks.org/longest-zig-zag-subsequence/

That’s all.

Feel free to comment/message in case of any questions.