1218. Longest Arithmetic Subsequence of Given Difference

Here is my discussion post.

It is easy to tell that the problem can be solved using dynamic programming solution. Since the length of array is 10^5, so if it is not linear, N^2 will be 10^10, I guess timeout will be a problem.

Here are highlights:

1. Take time to think about subproblems, dynamic programming solution;
2. My idea is to use extra space to save each value and its maximum length in prefix array;
3. Once I figure out step 2 to track prefix array each value with its maximum length hashmap, take time to write and test the code;
4. I made mistake to forget else case in second if clause in for loop; I need to push myself to test using my own test case first. Do not rely on Leetcode online judge.

public class Solution {
    public int LongestSubsequence(int[] arr, int difference) {
        var length = arr.Length; 
        
        // key - value
        // value - longest subsequence
        var dict = new Dictionary<int, int>(); 
        var dp = new int[length];
        
        for(int i = 0; i < length; i++)
        {
            var current = arr[i]; 
            var previous = current - difference; 
            int currentMax = 1; 
            
            if(dict.ContainsKey(previous))
            {
                currentMax = 1 + dict[previous];
            }
           
            dp[i] = currentMax; 
            
            if(dict.ContainsKey(current))
            {
                var previousLength = dict[current];
                if( currentMax > previousLength )
                {
                    dict[current] = currentMax; 
                }                
            } 
            else
                {
                    dict.Add(current, currentMax); 
                }
        }
         
        
        return dp.Max(); 
    }
}