1. 題目
給定一個未經(jīng)排序的整數(shù)數(shù)組，找到最長且連續(xù)遞增的子序列蛤育，并返回該序列的長度宛官。
連續(xù)遞增的子序列 可以由兩個下標 l 和 r（l < r）確定，如果對于每個 l <= i < r瓦糕，都有 nums[i] < nums[i + 1] 底洗，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是連續(xù)遞增子序列。
示例1:
輸入：nums = [1,3,5,4,7]
輸出：3
解釋：最長連續(xù)遞增序列是 [1,3,5], 長度為3咕娄。
盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續(xù)的亥揖，因為 5 和 7 在原數(shù)組里被 4 隔開。
示例2:
輸入：nums = [2,2,2,2,2]
輸出：1
解釋：最長連續(xù)遞增序列是 [2], 長度為1。
2. 思路
設計動態(tài)規(guī)劃的通用技巧是數(shù)學歸納法费变。
數(shù)學歸納法:假如我們想證明一個數(shù)學結(jié)論摧扇，那么先假設這個結(jié)論在k<n時成立，然后根據(jù)這個假設挚歧，想辦法推導證明出k=n的時候此結(jié)論成立扛稽。
類似的，我們設計動態(tài)規(guī)劃算法滑负，不是需要設計出一個dp數(shù)組嘛庇绽，可以假設dp[0...i-1]都已經(jīng)被計算出來了，然后思考怎么根據(jù)這些結(jié)果計算出dp[i]橙困？
首先要搞明白dp數(shù)組的含義，即dp[i]的值到底代表什么?
可以這樣定義:dp[i]表示以nums[i]這個數(shù)結(jié)尾的最長遞增子序列的長度耕餐。
根據(jù)這個定義凡傅，可以推出base case:dp[i]的初始值為1，我們的最終結(jié)果應該是dp數(shù)組中的最大值肠缔。
那么假設我們已經(jīng)知道了dp[0...4]的所有結(jié)果夏跷，如何通過這些結(jié)果計算出dp[5]呢?
只要找到前面那些結(jié)尾比nums[i]小的子序列，再拼上nums[i]即可明未。
for(int j=0; j<i; i++){
if(nums[i] > nums[j])
dp[i] = Math.max(dp[i],dp[j]+1);
}
當i=5時槽华，即可計算出dp[5]的值
3. 代碼
class Solution {
public int findLengthOfLCIS(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];
Arrays.fill(dp,1);
int max = 1;
for(int i=1; i<dp.length; i++){
if(nums[i] > nums[i-1]){
dp[i] = dp[i-1] + 1;
max = Math.max(max,dp[i]);
}
}
return max;
}
}
