給定一個整數數組 nums，傳回最長嚴格遞增的長度
子序列
.
範例1：
輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長的遞增子序列是[2,3,7,101]，因此長度是4。
範例2：
輸入：nums = [0,1,0,3,2,3]
輸出：4
範例 3：
輸入：nums = [7,7,7,7,7,7,7]
輸出：1
限制：
1 -10^4
跟進：你能想出一個以 O(n log(n)) 時間複雜度運行的演算法嗎？
原始頁
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);
}
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());
}
給定一個未排序的整數數組 nums，傳回最長連續遞增子序列（即子數組）的長度。子序列必須嚴格遞增。
連續遞增子序列由兩個索引l 和r (l < r) 定義，因此它是[nums[l], nums[l + 1], ..., nums[r - 1], nums [ r]] 並且對每個l <= i < r, nums[i] < nums[i + 1].
範例1：
輸入：nums = [1,3,5,4,7]
輸出：3
解釋：最長的連續遞增子序列是[1,3,5]，長度為3。
儘管 [1,3,5,7] 是一個遞增子序列，但它不是連續的，因為元素 5 和 7 由元素
分隔
4.
範例2：
輸入：nums = [2,2,2,2,2]
輸出：1
說明：最長連續遞增子序列為[2]，長度為1。注意，必須嚴格
增加。
限制：
1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
原始頁
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);
}
與上一題不同的是，本題我們只能考慮不斷增加子序列，簡化了流程。
以上是LeetCode Day 動態規劃 第 10 部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！
