区间覆盖问题

Leetcode-300 :Longest Increasing Subsequence

最长递增子序列问题，给定一个数组Arr{2，1，5，3，6，4，8，9，7}，那么其最长递增子序列为{2，5，6，8，9}，长度为5. 注意：子序列不要求出现的顺序必须连续。

Brute Force：

>//暴力搜索法：遍历所有的递增子序列，求出求最大长度， Time Complexity ： O(2^n)
>//可以使用备忘录memo减小复杂度 Time Complexity : O(n^2)
>class Solution {
   public int lengthOfLIS(int[] nums) {
       if(nums == null || nums.length==0) return 0;
       return dfs(nums,Integer.MIN_VALUE,0);
   }
   
   public int dfs(int[] nums,int prev,int idx){
       if(idx == nums.length) return 0;
       
       int token = 0;
       int untoken = 0;
       int next = 0;
       if(nums[idx]>prev){
           token = dfs(nums,nums[idx],idx+1)+1;
           untoken = dfs(nums,prev,idx+1);
       }else{
           next = dfs(nums,prev,idx+1);
       }
       return Math.max(token,Math.max(untoken,next));   
   }
>}

分析：

这是一道经典的动态规划题目，可以使用给一个数组 dp【N】，其中dp【i】表示 以Arr【i】为序列最后一个元素的最长递增子序列的长度。初始状态为dp【0】 = 1；对于任意一个状态dp【i】必定等于dp【prev】+ 1，其中prev < i && arr【prev】< arr【i】。遍历到dp【N-1】，记录最大值即可。

>int[] dp = new int[N];
>Arrays.fill(dp,1);
>int max = Integer.MIN_VALUE;
>for(int i=1;i<N;i++){
       for(int j=0;j<i;j++){
           if(arr[j] < arr[i]){
               dp[i] = Math.max(dp[i], dp[j]+1);
               max = Math.max(max. dp[i]);
           }
       }
>}
>//save result
>return max;