Question

link

Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that

A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible.

The sequence S1, S2, …, Sk is called an arithmetic progression if S(j+1) – S(j) is a constant.

Solution

This is a rather difficult Arithmetic Progression question.

The solution is 2-D DP.

The idea is to create a 2D table dp[n][n]. An entry dp[i][j] in this table stores LLAP with input[i] and input[j] as first two elements of AP(j > i).

The last column of the table is always 2. Rest of the table is filled from bottom right to top left.

To fill rest of the table, j (second element in AP) is first fixed. i and k are searched for a fixed j. If i and k are found such that i, j, k form an AP, then the value of dp[i][j] is set as dp[j][k] + 1.

Note that the value of dp[j][k] must have been filled before as the loop traverses from right to left columns.

The 2 difficult points of this question:

1. how to come up with the transation formula. (i.e. dp[i][j] = dp[j][k] + 1, when (i, j, k) forms a AP).
2. how to fill up all dp[i][j] in each loop of j. (Once inside the if-else, once outside the main while-loop)

Code

written by me

public int longest(int[] A) {
    int len = A.length;
    int[][] dp = new int[len][len];
    for (int i = 0; i < len; i++) {
        // the pair ending at last position is always a progression
        dp[i][len - 1] = 2;
    }
    int longest = 1;
    for (int j = len - 2; j >= 0; j--) {
        // for each j, find i and k that makes 1 progression
        int i = j - 1;
        int k = j + 1;
        while (i >= 0 && k < len) {
            int total = A[i] + A[k];
            if (total > 2 * A[j]) {
                // this is important!
                dp[i][j] = 2;
                i--;
            } else if (total < 2 * A[j]) {
                k++;
            } else {
                // found a valid progression triplet A(i, j, k)
                dp[i][j] = dp[j][k] + 1;
                longest = Math.max(longest, dp[i][j]);
                i--;
                k++;
            }
        }
        // this is important!
        while (i >= 0) {
            dp[i][j] = 2;
            i--;
            // If the loop was stopped due to k becoming more than
            // n-1, set the remaining dp[i][j] as 2
        }
    }
    return longest;
}