二刷 07/2022
Version #2 DP + binary search + prefix sum
比想象中的好写一点，关键点是binary search到start == end的时候，start点不一定是符合条件的，需要特殊讨论
另一个很大的bug是Arrays.fill(endings, new ArrayList<>())会造成所有的index都是同一个list，不能这么写
Time O(NlogN)
Space O(N)
Runtime: 10 ms, faster than 99.39% of Java online submissions for Number of Longest Increasing Subsequence.
Memory Usage: 47.1 MB, less than 5.28% of Java online submissions for Number of Longest Increasing Subsequence.
class Solution {
public int findNumberOfLIS(int[] nums) {
List<Pair<Integer, Integer>>[] endings = new ArrayList[nums.length];
for (int i = 0; i < endings.length; i++) {
endings[i] = new ArrayList<>();
}
for (int num : nums) {
int listIndex = findListIndex(endings, num);
List<Pair<Integer, Integer>> list = endings[listIndex];
int prevCount = 1;
if (listIndex > 0) {
List<Pair<Integer, Integer>> prevList = endings[listIndex - 1];
prevCount = findPrevCount(prevList, num);
}
int prefixSum = 0;
if (list.size() > 0) {
prefixSum = list.get(list.size() - 1).getValue();
}
list.add(new Pair<>(num, prefixSum + prevCount));
}
for (int i = endings.length - 1; i >= 0; i--) {
if (endings[i].size() > 0) {
return endings[i].get(endings[i].size() - 1).getValue();
}
}
return 0;
}
private int findPrevCount(List<Pair<Integer, Integer>> prevList, int num) {
int start = 0, end = prevList.size() - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (prevList.get(mid).getKey() >= num) {
start = mid + 1;
} else {
end = mid;
}
}
int total = prevList.get(prevList.size() - 1).getValue();
if (start == 0 && prevList.get(start).getKey() < num) {
return total;
}
return total - prevList.get(start - 1).getValue();
}
private int findListIndex(List<Pair<Integer, Integer>>[] endings, int num) {
int start = 0, end = endings.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
List<Pair<Integer, Integer>> midList = endings[mid];
if (midList.size() == 0) {
end = mid;
continue;
}
int lastElement = midList.get(midList.size() - 1).getKey();
if (lastElement < num) {
start = mid + 1;
} else {
end = mid;
}
}
if (endings[start].size() == 0 || endings[start].get(endings[start].size() - 1).getKey() >= num) {
return start;
}
return start + 1;
}
}
一刷 06/2022
Version #1 Naiive DP with two arrays
for each element in the array or on in the tree, they all carry three fields :
1) the maximum increasing / decreasing length ends at the current element,
2) its own value ,
3) the total number of maximum length,
Time O(N^2)
Space O(N)
Runtime: 33 ms, faster than 43.44% of Java online submissions for Number of Longest Increasing Subsequence.
Memory Usage: 44.3 MB, less than 53.55% of Java online submissions for Number of Longest Increasing Subsequence.
class Solution {
public int findNumberOfLIS(int[] nums) {
int[] len = new int[nums.length];
int[] count = new int[nums.length];
int maxLen = 0;
int maxCount = 0;
for (int end = 0; end < nums.length; end++) {
len[end] = 1;
count[end] = 1;
for (int prev = end - 1; prev >= 0; prev--) {
if (nums[prev] >= nums[end]) {
continue;
}
// nums[prev] < nums[end] - can concatenate
if (len[prev] + 1 > len[end]) {
len[end] = len[prev] + 1;
count[end] = count[prev];
} else if (len[prev] + 1 == len[end]) {
count[end] += count[prev];
}
}
if (len[end] == maxLen) {
maxCount += count[end];
} else if (len[end] > maxLen) {
maxLen = len[end];
maxCount = count[end];
}
}
return maxCount;
}
}
