Sponsored
Sponsored
This approach involves using a 2D dynamic programming array to keep track of the lengths of arithmetic subsequences ending at different indices with various common differences. The outer loop iterates over end indices while the inner loop considers all pairs of start and end indices to update the subsequence lengths.
Time Complexity: O(n^2)
Space Complexity: O(n^2), where n is the size of the input array.
1import java.util.HashMap;
2import java.util.Map;
3
4public class LongestArithmeticSubsequence {
5 public static int longestArithSeqLength(int[] nums) {
6 if (nums.length <= 2) return nums.length;
7 Map<Integer, Integer>[] dp = new HashMap[nums.length];
8 int maxLength = 2;
9 for (int i = 0; i < nums.length; i++) {
10 dp[i] = new HashMap<>();
11 for (int j = 0; j < i; j++) {
12 int diff = nums[i] - nums[j];
13 dp[i].put(diff, dp[j].getOrDefault(diff, 1) + 1);
14 maxLength = Math.max(maxLength, dp[i].get(diff));
15 }
16 }
17 return maxLength;
18 }
19
20 public static void main(String[] args) {
21 int[] nums = {3, 6, 9, 12};
22 System.out.println(longestArithSeqLength(nums));
23 }
24}The Java solution uses an array of HashMaps to store the lengths of arithmetic sequences by their common differences. For each number `nums[i]`, it checks all previous numbers `nums[j]` to see if a sequence with the same difference already exists.
This approach uses a simplified dynamic programming technique with HashMaps and tracks differences and their counts for each number. By leveraging HashMap structures, we manage subsequence lengths more efficiently and avoid using unnecessary space for non-existent differences.
Time Complexity: O(n^2)
Space Complexity: O(n^2) in the worst case but often much less due to sparse differences.
1
In Python, we utilize dictionaries for compactness and flexibility, addressing only meaningful key-difference pairs at each step to maintain the subsequence lengths efficiently.