# Longest Arithmetic Progression in Java

The longest Arithmetic Progression problem involves identifying the longest sequence of elements in a sorted array where the difference between consecutive elements remains constant and returning the length of this sequence.

Example:

Input: Array: {3, 6, 9, 12, 15}

Output: Length of the longest arithmetic progression: 5

Explanation: In the given array {3, 6, 9, 12, 15}, every consecutive pair of elements forms an arithmetic progression with a common difference of 3. Thus, the entire array itself forms an arithmetic progression of length 5.

## Approach: Brute Force

### Algorithm

Step 1: Sorted integer array arr.

Step 2: Set maxLength to 2, indicating the minimum length of an arithmetic progression.

Step 3: For each pair of elements arr[i] and arr[j], where i and j iterate over the array.

Step 4: Calculate the difference between arr[j] and arr[i].

Step 5: Increment the current progression length if the next term exists in the sequence.

Step 6: Update maxLength with the maximum length found during the iteration.

Step 7: Return maxLength as the length of the longest arithmetic progression subsequence.

FileName: LongestAP.java

`public class LongestAP {    static int longestAP(int[] arr) {        int maxLength = 2;        // Loop through each pair of elements in the array to find the common difference        for (int i = 0; i < arr.length - 2; i++) {            for (int j = i + 1; j < arr.length - 1; j++) {                int diff = arr[j] - arr[i]; // Calculate the common difference between elements i and j                int length = 2; // Initialize the length of the current arithmetic progression to 2                int nextTerm = arr[j] + diff; // Calculate the next term in the potential arithmetic progression                // Iterate through the remaining elements in the array to check if they form an arithmetic progression                for (int k = j + 1; k < arr.length; k++) {                    if (arr[k] == nextTerm) {                        length++;                        nextTerm += diff; // Calculate the next term in the potential arithmetic progression                    }                }                maxLength = Math.max(maxLength, length); // Update the maximum length if needed            }        }        return maxLength;    }    public static void main(String[] args) {        int[] arr = {3, 6, 9, 12, 15};        System.out.println("Length of the longest arithmetic progression: " + longestAP(arr));    }}`

Output:

`Length of the longest arithmetic progression: 5`

Complexity Analysis: The code has a time complexity of O(n^3), where n is the length of the input array. The space complexity is O(1) as it uses a constant amount of extra space regardless of the input size.

## Approach: Dynamic Programming

### Algorithm

Step 1: Accept a sorted integer array.

Step 2: If the array length is 2 or less, return the length. Otherwise, set the maximum length to 2.

Step 3: Create a 2D array to store lengths of arithmetic progressions ending at each pair of indices.

Step 4: Traverse pairs of elements, updating the array with lengths of arithmetic progressions.

Step 5: Return the maximum length found as the result.

FileName: LongestAP.1java

`import java.util.Arrays;public class LongestAP1 {    static int longestAP(int[] arr) {        int n = arr.length;        if (n <= 2)            return n;        int maxLength = 2; // Initialize the result to 2 (minimum length of AP)        // Dynamic programming approach        int[][] dp = new int[n][n];        // Initialize all values to 2 since every pair forms an AP of length 2        for (int i = 0; i < n; i++)            Arrays.fill(dp[i], 2);        // Iterate over pairs of elements to find the longest AP        for (int j = n - 2; j >= 1; j--) {            int i = j - 1;            int k = j + 1;            while (i >= 0 && k < n) {                if (arr[i] + arr[k] < 2 * arr[j])                    k++;                else if (arr[i] + arr[k] > 2 * arr[j]) {                    dp[i][j] = 2;                    i--;                } else {                    // If arr[i] + arr[k] == 2 * arr[j], then arr[i], arr[j], arr[k] form an AP                    dp[i][j] = dp[j][k] + 1;                    maxLength = Math.max(maxLength, dp[i][j]);                    i--;                    k++;                }            }        }        return maxLength;    }    public static void main(String[] args) {        int[] arr = {3, 6, 9, 12, 15};        System.out.println("Length of the longest arithmetic progression: " + longestAP(arr));    }}`

Output:

`Length of the longest arithmetic progression: 5`

Complexity Analysis: The code has time complexity of O(n^2) and a space complexity of O(n^2), where n is the length of the input array.