題目描述：
給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度稚虎。
示例:
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4云头。
解法：
動態(tài)規(guī)劃
狀態(tài)轉(zhuǎn)移方程：
dp[i]表示數(shù)組前i個數(shù)字的最長上升子序列長度
設(shè)j屬于[0,i)，考慮每輪計算dp[i]時乌询，遍歷[0,i)做以下判斷：
1.當nums[i]>nums[j]時,nums[i]可以接在nums[j]之后贮预，此時nums[i] = nums[j]+1
2.當nums[i]<=nums[j]時毛仪，nums[i]不能接在nums[j]之后，此時上升子序列不存在对粪，跳過
總結(jié)：
dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length==0) return 0;
int[] dp = new int[nums.length];
//初始化dp數(shù)組中的每個元素都為1右冻，因為1個單獨的元素也是一個子序列
Arrays.fill(dp,1);
int max = 0;
for(int i=0;i<nums.length;i++){
for(int j=0;j<i;j++){
//對[0,j)區(qū)間的元素進行遍歷装蓬，若nums[i]>nums[j]，說明nums[i]可接在nums[j]后面形成一個上升子序列
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
max = Math.max(max,dp[i]);
}
return max;
}
}
