題目
給定一個(gè)整數(shù)序列，找到最長(zhǎng)上升子序列（LIS）苛茂，返回LIS的長(zhǎng)度已烤。
說明最長(zhǎng)上升子序列的定義：
最長(zhǎng)上升子序列問題是在一個(gè)無序的給定序列中找到一個(gè)盡可能長(zhǎng)的由低到高排列的子序列，這種子序列不一定是連續(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
分析
方法一：動(dòng)態(tài)規(guī)劃
用dp[i]表示前i個(gè)數(shù)的最長(zhǎng)上升子序列，可以循環(huán)判斷净刮，每增加一個(gè)數(shù)剥哑，就要循環(huán)更新一遍前面的dp[]數(shù)組
fang
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=1;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(max, dp[i]);
}
return max;
}
}
方法二：
用一個(gè)list來存儲(chǔ)元素：
Paste_Image.png
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==0)
return 0;
ArrayList<Integer> list = new ArrayList<Integer>();
for(int num: nums){
if(list.size()==0){
list.add(num);
}else if(num>list.get(list.size()-1)){
list.add(num);
}else{
int i=0;
int j=list.size()-1;
while(i<j){
int mid = (i+j)/2;
if(list.get(mid) < num){
i=mid+1;
}else{
j=mid;
}
}
list.set(j, num);
}
}
return list.size();
}
}
