300. Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing
subsequence
.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints:
1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
Original Page
Wrong Code
int start = nums[0];
int pre = nums[0];
int preMax = nums[0];
int cnt = 1;
int max = 1;
for(int i=1; i<nums.length; i++){
if(nums[i] < start){
max = Math.max(max, cnt);
start = nums[i];
cnt = 1;
}
else if(nums[i] > pre){
cnt ++;
}
pre = nums[i];
System.out.println(“cur:”+nums[i] + ” pre:”+pre+ ” count:” + cnt);
}
return Math.max(max, cnt);
}
Fix bug
Learn From others treemap
TreeMap<Integer,Integer> map = new TreeMap<>();
map.put(Integer.MIN_VALUE,0);
for(int i: nums)
{
map.put(i,map.get(map.lowerKey(i))+1);
while(map.higherKey(i)!=null && map.get(map.higherKey(i))<=map.get(i))
{
map.remove(map.higherKey(i));
}
}
return map.get(map.lastKey());
}
674. Longest Continuous Increasing Subsequence
Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.
A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], …, nums[r – 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].
Example 1:
Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.
Example 2:
Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly
increasing.
Constraints:
1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
Original Page
Greedy Algorithm
if(nums.length < 1){
return 0;
}
int res = 1;
int cnt = 1;
int pre = nums[0];
for(int i=1; i<nums.length; i++){
if(nums[i] > pre){
cnt++;
}else{
res = Math.max(res, cnt);
cnt = 1;
}
// System.out.println(“cur: ” + nums[i] + ” pre:” + pre + ” count:” + cnt);
pre = nums[i];
}
return Math.max(res, cnt);
}
Dynamic Programming
Different from the previous question, in this question we could only consider continuously increasing subsequences, which simplifies the process.
