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.