1218. Longest Arithmetic Subsequence of Given Difference

T: O(n)
S: O(n)

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int num : arr) {
            map.put(num, map.getOrDefault(num-difference, 0)+1);
            res = Math.max(res, map.get(num));
        }
        return res;
    }
}

/*
dp[i] be the maximum length of a subsequence with given difference 


dp[i] = dp[i-k]+1


[1,2,3,4]

3 - 1 = 2, 3 from 2, check 2 is existed? existed, dp[3] = len of dp[2] + 1, or just dp[3] = 1

2 - 1 = 1, 2 from 1, check 1 is existed? existed, len of dp[1] + 1


[1,3,5,7], diff 1

7 - 1 = 6, check 6 is existed? not existed dp[7] = 1

5 - 1 =4, check 4 is existed? not existed dp[5] = 1
...

[1,5,7,8,5,3,4,2,1], diff -2

3 +2 = 5 , check 5 is existed? existed, dp[3] = len of dp[5] + 1, or just dp[3] = 1
5+2 = 7,  check 7 is existed? existed

subseqence's record are not continuous, so used hashmap<num, len>

T: O(n)
S: O(n)
*/

1/3 version, explain is more

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer, Integer> dp = new HashMap<>();
        
        int res = 0;
        for (int num : arr) {
            int count = dp.getOrDefault(num - difference, 0)+1;
            dp.put(num, count);
            res = Math.max(res, count);
        }
        return res;
    }
}

/*
fix diff

how to know diff?
ex: use a[1] - a[0], check is it equals to diff
so the following data depends on pre data, so it's a dp question

Input: arr = [1,2,3,4], difference = 1

use hashmap store, data, count

because 
Input: arr = [1,3,5,7], difference = 1
Output: 1
The longest arithmetic subsequence is any single element

so when first data, its' count is 1

1 1
2.1+1   2- diff = 2-1 = 1
3 2+1
4 3+1 => max(0~n-1, dp[n-1] is result


[1,3,5,7] diff = 1

1 1
3 1
5 1
7 1 => max(0~n-1, dp[n-1] is result

[1,5,7,8,5,3,4,2,1], difference = -2

1 1
5.1   5-(-2) = 7
7 1    7+2 = 9
8 1     10
5 2     7
3 3      5
4 1      6
2 2       4 
1 4       3   => max(0~n-1, dp[n-1] is result

T: O(n)
S: O(n)
*/