This content originally appeared on DEV Community and was authored by Flame Chan
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
public int lengthOfLIS(int[] nums) {
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
public int lengthOfLIS(int[] nums) {
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
public int findLengthOfLCIS(int[] nums) {
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.
This content originally appeared on DEV Community and was authored by Flame Chan
Flame Chan | Sciencx (2024-07-19T03:18:27+00:00) LeetCode Day 36 Dynamic Programming Part 10. Retrieved from https://www.scien.cx/2024/07/19/leetcode-day-36-dynamic-programming-part-10/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.