LeetCode上最長遞增子序列，中等難度記錄下解題思路
這是一道LIS題目，LIS（Longest Increasing Subsequence）最長上升（不下降）子序列。
假設(shè)傳入一個數(shù)組nums = [1,0,1,3,8,8,1,8]從i = 0開始取子數(shù)組，要計算能取到的最長遞增子數(shù)組
這里開始引入動態(tài)規(guī)劃的概念，擁有一個數(shù)組dp，dp中的dp[i]對應(yīng)的是i位置的數(shù)組能獲取的最長遞增數(shù)組
這里發(fā)現(xiàn)了一個不錯的線上LIS演示網(wǎng)站，結(jié)合這個網(wǎng)站來看整個過程
通過內(nèi)外兩層循環(huán)來解題外層循環(huán)i和內(nèi)層循環(huán)j
例如
當(dāng)求
i = 3 nums[3] = 3的情況，需要遍歷[0,3-1]的數(shù)和3對比對比
j= 0 nums[0] = 1和i = 3 nums[3] = 3的情況3 > 1所以這個子串是能夠成立的，并且由于
dp[0] = 1，那么當(dāng)j= 0 i =3的情況下最大的子串為Math.max(dp[i],dp[j]+1) 此時dp[3] = 2，之后j++對比
j= 1 nums[1] = 0和i = 3 nums[3] = 3的情況3 > 0，但此時
Math.max(dp[i],dp[j]+1) = Math.max(2,1+1)此時還是dp[3] = 2對比
j= 2 nums[2] = 1和i = 3 nums[3] = 3的情況3 > 1，但此時
Math.max(dp[i],dp[j]+1) = Math.max(2,2+1)此時還是dp[3] = 3
所以最后總結(jié)下來
- 需要一個dp數(shù)組，默認(rèn)全部填充1
- 用雙重循環(huán)填充dp數(shù)組，每次
i位置的填充需要遍歷nums[0,i-1]范圍內(nèi)的數(shù)據(jù)，同時比較dp[j] = Math.max(dp[i],dp[j]+1)
var lengthOfLIS = function(nums) {
// 保存長度
let n = nums.length;
if(n == 0) return 0
// 創(chuàng)建個對應(yīng)長度的數(shù)組，并且都填充1,
// 填充1是子數(shù)組最差也是包含自己，那么長度怎么都是1
let dp = new Array(n).fill(1);
// 需要返回的值
let max = 0;
// 遍歷整個數(shù)組
for(let i = 0;i < n;i++){
// 遍歷[0,i-1]范圍的數(shù)
for(let j = 0;j < i;j++){
//如果成立nums[j] < nums[i]，那么這個數(shù)組就是遞增的
if(nums[j] < nums[i]){
// 對比下之前的長度，和這次能夠生成的長度
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
max = Math.max(max,dp[i]);
}
return max;
};
