Find longest Arithmetic Progression in an integer array A of size N, and return its length.
More formally, find longest sequence of indices, 0 < i1 < i2 < … < ik < ArraySize(0-indexed) such that sequence A[i1], A[i2], …, A[ik] is an Arithmetic Progression.
Arithmetic Progression is a sequence in which all the differences between consecutive pairs are the same, i.e sequence B[0], B[1], B[2], …, B[m - 1] of length m is an Arithmetic Progression if and only if B[1] - B[0] == B[2] - B[1] == B[3] - B[2] == … == B[m - 1] - B[m - 2]
Note: The common difference can be positive, negative or 0.
Input Format:
The first and the only argument of input contains an integer array, A.
Output Format:
Return an integer, representing the length of the longest possible arithmetic progression.
Constraints:
1 <= N <= 1000
1 <= A[i] <= 1e9
Examples:
Input 1:
A = [3, 6, 9, 12]
Output 1:
4
Explanation 1:
[3, 6, 9, 12] form an arithmetic progression.
Input 2:
A = [9, 4, 7, 2, 10]
Output 2:
3
Explanation 2:
[4, 7, 10] form an arithmetic progression.
Solution:
Time: O(n) Space: O(n^2)
public class Solution { // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY public int solve(final int[] A) { int n = A.length; // dp[i] = longest length of arithmetic progression ending at i // diff[i] = diff that provides max length of progression ending at i // dp[i] = max(dp[i], 1 + dp[j] if diff[j] = A[i] - A[j]) // max(dp[n]) if (n <= 2) return n; int[] dp = new int[n]; Set<Integer>[] diff = new HashSet[n]; int max = 1; dp[0] = 1; dp[1] = 2; diff[0] = new HashSet<>(Arrays.asList(A[0])); diff[1] = new HashSet<>(Arrays.asList(A[1] - A[0])); for (int i = 2; i < n; i ++) { dp[i] = 2; for (int j = 0; j < i; j ++) { if (diff[i] == null) { diff[i] = new HashSet<>(Arrays.asList(A[i] - A[j])); } if (diff[j].contains(A[i] - A[j])) { if (dp[j] >= dp[i]) { dp[i] = 1 + dp[j]; diff[i] = diff[j]; } else if (dp[j] + 1 == dp[i]) { diff[i].add(A[i] - A[j]); } } else if (dp[i] == 2) { diff[i].add(A[i] - A[j]); } } max = Math.max(max, dp[i]); } // System.out.println(Arrays.toString(dp)); // System.out.println(Arrays.toString(diff)); return max; } }