Version #1 primitive DP
O(n^2)
We define T[i] as the longest increasing subsequence whose maximum number is nums[i]
T[i] = for every j < i, maximum T[j] + 1 where nums[j] < nums[i]
一刷
42.69%
public class Solution {
public int lengthOfLIS(int[] nums) {
// write your code here
if (nums == null || nums.length == 0) return 0;
int[] count = new int[nums.length];
count[0] = 1;
int max = 1;
for (int curr = 0; curr < nums.length; curr++) {
count[curr] = 1;
for (int prev = 0; prev < curr; prev++) {
if (nums[prev] < nums[curr]) {
count[curr] = Math.max(count[curr], count[prev] + 1);
}
}
max = Math.max(max, count[curr]);
}
return max;
}
}
二刷
49.00 %
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int longest = 1;
// dp[i] -> LIS end with index i
// for all a < i && nums[a] < nums[i], dp[i] = Max(dp[a]) + 1
int[] dp = new int[nums.length];
dp[0] = 1;
for (int end = 1; end < nums.length; end++) {
int max = 0;
for (int start = end - 1; start >= 0; start--) {
if (nums[start] < nums[end]) {
max = Math.max(dp[start], max);
}
}
dp[end] = max + 1;
longest = Math.max(longest, dp[end]);
}
return longest;
}
}
Version #2 DP with Binary Search
Time O(nlogn)
九章讲解
89.86%
一刷
思路很简单不知道为什么网上的所有讲解都讲的特别不清楚。。。
就是维护一个minEnd array
index代表的是subsequence length
value代表的是所有能够组成当前valid subsequence的可能性中那个最小的end point
譬如给一个array 5 2 3 6 4
当遍历到6的时候，所有能够使subsequence为2的结果有 5 6，2 3，2 6
这里的3 就是minimum end point
为什么要保留这个值呢？因为对于所有后来的数，凡是大于其他possible end point的一定大于minimum，但是大于minimum的却不一定大于其他possible end point
所以这个minimum保证了最大的后续sequence 的potential
当current point 大于当前最大length的minEnd时，证明subarray可以被expand，于是length++
若小于等于当前最大length,则之前的某一个midEnd一定可以被更新
【注意】这里写了一个bug就是binarySearch找的是firstLargerIndex但是没考虑有duplicates的情况
若考虑duplicates则应该是第一个大于等于target的index
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
//countIndex -> length - 1
int[] minEnd = new int[nums.length];
int len = 0;
minEnd[0] = nums[0];
for (int curr = 1; curr < nums.length; curr++) {
if (nums[curr] < minEnd[0]) {
minEnd[0] = nums[curr];
} else if (nums[curr] > minEnd[len]) {
len++;
minEnd[len] = nums[curr];
} else {
int firstLargerIndex = binarySearch(minEnd, len, nums[curr]);
minEnd[firstLargerIndex] = nums[curr];
}
}
return len + 1;
}
//search between [0,len]
//Consider the case with duplicates
private int binarySearch(int[] minEnd, int len, int target) {
if (len == 0) return 0;
int start = 0, end = len;
int mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (minEnd[mid] > target) end = mid;
else start = mid;
}
if (minEnd[start] >= target) return start;
return end;
}
}
二刷
不如一刷写的好
应该找到第一个大于等于的值
94.34 %
class Solution {
public int lengthOfLIS(int[] nums) {
// We have some repeat work when search for previous nums
// Given an array 2, 5, 3 ...
// We can either choose 2, 3 to construct an array of length 2, or choose 2, 5 to construct an array of length 2
// We are always using the smaller one
if (nums == null || nums.length == 0) {
return 0;
}
// minEnd[i] -> minimum end number to form a LIS of length i
// Find the 1st index greater than current number, replace by the current number
// If not found, increase max length
int[] minEnd = new int[nums.length];
minEnd[0] = nums[0];
int max = 0;
//[4,10,4,3,8,9]
// max 0 1 2 3 4 5
// minEnd 4 10
for (int i = 1; i < nums.length; i++) {
int start = 0;
int end = max;
while (start < end) {
int mid = start + (end - start) / 2;
if (minEnd[mid] <= nums[i]) {
start = mid + 1;
} else {
end = mid;
}
}
if (minEnd[start] >= nums[i] && (start == 0 || minEnd[start - 1] < nums[i])) {
minEnd[start] = nums[i];
} else if (minEnd[start] < nums[i]) {
max++;
minEnd[max] = nums[i];
}
}
return max + 1;
}
}
三刷 06/2022
Version #1 Naiive DP
Time O(N^2)
Space O(N)
Runtime: 68 ms, faster than 57.46% of Java online submissions for Longest Increasing Subsequence.
Memory Usage: 44.7 MB, less than 30.22% of Java online submissions for Longest Increasing Subsequence.
class Solution {
public int lengthOfLIS(int[] nums) {
// dp[i] - longest increasing subsequence ending with nums[i]
int[] dp = new int[nums.length];
int globalMax = 0;
for (int end = 0; end < nums.length; end++) {
int prevMax = 0;
for (int prev = end - 1; prev >= 0; prev--) {
if (nums[prev] < nums[end]) {
prevMax = Math.max(prevMax, dp[prev]);
}
}
dp[end] = prevMax + 1;
globalMax = Math.max(globalMax, dp[end]);
}
return globalMax;
}
}
Version #2 Binary Search
注意相等的情況是需要非常注意的
一定是找到第一个大于等于num的minEnd，而不是大于的
因为如果两个数相等是不能接在一起的
Time O(NlogN)
Space O(N)
Runtime: 7 ms, faster than 80.35% of Java online submissions for Longest Increasing Subsequence.
Memory Usage: 44 MB, less than 70.52% of Java online submissions for Longest Increasing Subsequence.
class Solution {
public int lengthOfLIS(int[] nums) {
// We keep a minEnd array represents the minimum end number that could be to construct a sequence with that length
// The minEnd array is increasing
// Given a number, we need to see if it can replace one of the minEnd - find the first index that is larger than or equals to the number, and replace that number
int[] minEnd = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
minEnd[i] = Integer.MAX_VALUE;
}
int max = 0;
for (int i = 0; i < nums.length; i++) {
int p = insertPosition(minEnd, nums[i]);
minEnd[p] = nums[i];
max = Math.max(max, p + 1);
}
return max;
}
private int insertPosition(int[] minEnd, int num) {
int start = 0, end = minEnd.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (minEnd[mid] < num) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
}
No comments:
Post a Comment