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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int LongestArithSeqLength(int[] nums) {
6 if (nums.Length <= 2) return nums.Length;
7 var dp = new Dictionary<int, int>[nums.Length];
8 int maxLength = 2;
9 for (int i = 0; i < nums.Length; i++) {
10 dp[i] = new Dictionary<int, int>();
11 for (int j = 0; j < i; j++) {
12 int diff = nums[i] - nums[j];
13 if (dp[j].ContainsKey(diff)) {
14 dp[i][diff] = dp[j][diff] + 1;
15 } else {
16 dp[i][diff] = 2;
17 }
18 maxLength = Math.Max(maxLength, dp[i][diff]);
19 }
20 }
21 return maxLength;
22 }
23
24 public static void Main(string[] args) {
25 int[] nums = {3, 6, 9, 12};
26 var sol = new Solution();
27 Console.WriteLine(sol.LongestArithSeqLength(nums));
28 }
29}The C# version employs an array of dictionaries to map the length of arithmetic sequences by their differences. By iterating over all pairs of indices and computing differences, it checks and updates `dp[i]` to reflect the new lengths of the sequences.
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.
1using System.Collections.Generic;
public class Solution {
public int LongestArithSeqLength(int[] nums) {
if (nums.Length <= 2) return nums.Length;
var dp = new Dictionary<int, int>[nums.Length];
int maxLength = 2;
for (int i = 0; i < nums.Length; i++) {
dp[i] = new Dictionary<int, int>();
for (int j = 0; j < i; j++) {
int diff = nums[i] - nums[j];
if (dp[j].ContainsKey(diff)) {
dp[i][diff] = dp[j][diff] + 1;
} else {
dp[i][diff] = 2;
}
maxLength = Math.Max(maxLength, dp[i][diff]);
}
}
return maxLength;
}
public static void Main() {
int[] nums = {9, 4, 7, 2, 10};
var sol = new Solution();
Console.WriteLine(sol.LongestArithSeqLength(nums));
}
}This C# code handles the longest arithmetic subsequence problem by establishing dictionaries for each element in the array, keeping score of different arithmetic sequences iteratively and effectively.