LintCode 最长上升子序列题目分析

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;
    }
}

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();
    }
}