Sponsored
Sponsored
This approach uses a hash map (or dictionary) to keep track of the longest subsequence length that can be achieved ending with a specific value. For each element in the array, we check if there is an arithmetic subsequence ending with the element minus the given difference. If such a subsequence exists, we calculate the current subsequence length. Otherwise, we start a new subsequence from this element.
Time Complexity: O(n), where n is the length of arr. We iterate over the array once.
Space Complexity: O(n), where n is the number of distinct elements in arr stored in the dictionary.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int LongestSubsequence(int[] arr, int difference) {
6 Dictionary<int, int> dp = new Dictionary<int, int>();
7 int max_length = 0;
8 foreach (int num in arr) {
9 if (!dp.ContainsKey(num)) dp[num] = 0;
10 dp[num] = dp.GetValueOrDefault(num - difference, 0) + 1;
11 max_length = Math.Max(max_length, dp[num]);
12 }
13 return max_length;
14 }
15}A C# solution using a Dictionary, where each iteration updates subsequences by checking the possible previous number that can form a valid arithmetic sequence.
This approach utilizes an array to store information about each possible element value scaled according to the constraints. For each element in arr, determine if there is a previous subsequence that can be extended using direct array access.
Time Complexity: O(n), where n is the length of arr.
Space Complexity: O(1) (constant size array mentioned in constraints).
#include <algorithm>
using namespace std;
int longestSubsequence(vector<int>& arr, int difference) {
int dp[20001] = {0};
int max_length = 0;
int offset = 10000;
for (int num : arr) {
int idx = num + offset;
int prev_idx = num - difference + offset;
dp[idx] = dp[prev_idx] + 1;
max_length = max(max_length, dp[idx]);
}
return max_length;
}This C++ solution aligns the array dp based on the constraint bounds, using simple array indexing to keep track of subsequences, which improves performance over hashmap lookups.