How can dynamic programming be applied to solve the Longest Arithmetic Progression problem? Implement the solution.?

The Longest Arithmetic Progression problem asks to find the length of the longest subsequence of an array that forms an arithmetic progression. For example, given the array ‘[3, 6, 9, 12]‘, the longest arithmetic progression is ‘[3, 6, 9, 12]‘ with a length of 4.

Dynamic programming can be applied to solve this problem using a bottom-up approach. We can define a 2D array ‘dp[i][j]‘ where ‘dp[i][j]‘ represents the length of the longest arithmetic progression that ends at indices ‘i‘ and ‘j‘ of the array.

To populate this array, we can iterate over each pair of indices ‘(i, j)‘ where ‘j > i‘. If the difference between ‘arr[j]‘ and ‘arr[i]‘ is the same as the difference between the previous pair of numbers in the arithmetic progression, then we can add 1 to ‘dp[i][j]‘. Otherwise, ‘dp[i][j]‘ is initialized to 2 (since we have found two numbers in the arithmetic progression so far).

After populating the ‘dp‘ array, we can find the maximum value in it and return it as the length of the longest arithmetic progression in the array.

Here is an example implementation in Java:

public static int longestArithSeqLength(int[] arr) {
    int n = arr.length;
    int[][] dp = new int[n][n];
    int maxLength = 2;

    // Initialize dp array
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[i], 2);
    }

    // Populate dp array
    for (int j = 1; j < n; j++) {
        for (int i = 0; i < j; i++) {
            for (int k = 0; k < i; k++) {
                if (arr[i] - arr[k] == arr[j] - arr[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[k][i] + 1);
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }
    }

    return maxLength;
}

In this implementation, we iterate over each pair of indices ‘(i, j)‘ where ‘j > i‘ and then iterate over all indices ‘k‘ less than ‘i‘. If the difference between ‘arr[j]‘ and ‘arr[i]‘ is the same as the difference between ‘arr[i]‘ and ‘arr[k]‘, then we can update ‘dp[i][j]‘ with the maximum length of the arithmetic progression ending at index ‘i‘ and ‘j‘. Finally, we update ‘maxLength‘ with the maximum value in the ‘dp‘ array.

This implementation has a time complexity of O(n³) and a space complexity of O(n²). However, it can be optimized to have a time complexity of O(n²) using a hash table to store the index of each number in the array.