05 August 2008
给一个整数数组 arr 和一个整数差，返回 arr 中最长子序列的长度，这是一个算术序列，使得子序列中相邻元素之间的差等于差。
子序列是可以通过删除一些元素或不删除元素而不改变剩余元素的顺序从 arr 派生的序列。
We create a map where we keep track of the maximum length of sequence ending at each of the elements of the array. We iterate through the array. If the current element is n then we try to get the sequence length for n-diff. If we find it then it means the max sequence length ending at n is the length of the sequence ending at n-diff plus one. If we don’t find n-dff in the map then we know that max length of sequence ending at n should be 1 and we put it in the map (to be used for computing sequence length for later elements).
1
2
3
4
5
6
7
8
9
class Solution {
public int longestSubsequence(int[] arr, int diff) {
var map = new HashMap<Integer,Integer>();
for (int num: arr) {
map.put(num, map.getOrDefault(num - diff, 0) + 1);
}
return map.values().stream().mapToInt(Integer::intValue).max().getAsInt();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int longestSubsequence(int[] arr, int difference) {
Map<Integer, Integer> seqCounts = new HashMap<>();
int max = 0;
for (int a : arr) {
int aSeqCount = 1; // First we assume max sequence from current number is 1
if (seqCounts.containsKey(a-difference)) { // Try to find if we have next num in seq from a, stored for a - diff
aSeqCount += seqInLeft.get(a-difference); // If we find, then that number's value is the seq count so far, add into a's count
}
seqCounts.put(a, aSeqCount); // Anyways put seq count against current number, a
max = Math.max(max, aSeqCount); // Keep track of max
}
return max;
}
}