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;
}