題目
給定一個整數(shù)序列，找到最長上升子序列（LIS），返回LIS的長度窗轩。
說明
最長上升子序列的定義：
最長上升子序列問題是在一個無序的給定序列中找到一個盡可能長的由低到高排列的子序列，這種子序列不一定是連續(xù)的或者唯一的。https://en.wikipedia.org/wiki/Longest_increasing_subsequence
樣例
給出 [5,4,1,2,3]难咕，LIS 是 [1,2,3]，返回 3
給出 [4,2,4,5,3,7]距辆，LIS 是 [2,4,5,7]余佃，返回 4
分析
dp[i]：記錄前i個子序列最長的上升子序列，每加入一個數(shù)跨算，可能很多子序列都會發(fā)生變化爆土，所以要一個內(nèi)層循環(huán)判斷，如果大于诸蚕，就在之前的基礎(chǔ)上加1步势，最后用一個變量記錄最大值。
代碼
dp[i]：記錄前i個子序列最長的上升子序列挫望，每加入一個數(shù)立润，可能很多子序列都會發(fā)生變化，所以要一個內(nèi)層循環(huán)判斷媳板，如果大于桑腮，就在之前的基礎(chǔ)上加1，最后用一個變量記錄最大值蛉幸。
public class Solution {
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
public int longestIncreasingSubsequence(int[] nums) {
if(nums==null || nums.length<1) return 0;
int[] dp = new int[nums.length];
dp[0] = 1;
int max = dp[0];
for(int i=0;i<nums.length;i++) {
dp[i] = 1;
for(int j=0;j<i;j++) {
if(nums[i]>nums[j])
dp[i] = Math.max(dp[i], dp[j]+1);
}
max = Math.max(dp[i], max);
}
return max;
}
}
