【力扣刷题第四天-2】 最长递增子序列

前言一、题目描述二、解题思路

1. 动态规划2. 贪心 + 二分查找 三、示例代码

1. 动态规划2. 贪心 + 二分查找 总结

  本题主要考查 动态规划 算法。

提示：以下是本篇文章正文内容，编程语言为Java

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

链接：最长递增子序列

  1）确定dp数组的含义。 我们用 dp[i]表示以 num[i] 结尾的最长严格递增子序列的长度。
  2）推导状态转移方程。 我们从前到后计算 dp 数组的值，在计算 dp[i] 之前，我们已经计算出 dp[0…i−1] 的值，因此，可得状态转移方程：
  3）分析边界条件，初始化 dp 数组。 很容易想到 dp[0]=1
  4）自底向上，由简至难的填充 dp 数组。

  考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
  基于上面的贪心策略，我们维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len=1 ，d[1] = nums[0]。
  我们遍历数组：
  1） 当 num[i] > dp[len] 时，则直接加入到 dp 数组末尾，并且 len = len + 1；
  2） 当 num[i] <= dp[len] 时，我们需要更新 dp 数组，找到一个索引最小的比 num[i] 大的 dp[j]，将它更新为 num[i]，可以用二分法加速查找。因为 dp 数组是递增的，所以要找索引最小的更新。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp=new int[nums.length];
        dp[0]=1;
        int ans=1;
        for(int i=1;i=0;j--){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[j]+1,dp[i]);
                    ans=Math.max(dp[i],ans);
                }
            }
            ans=Math.max(dp[i],ans);
         }
         return ans;
        }

    }

class Solution {
    public int lengthOfLIS(int[] nums) {
        int []dp =new int[nums.length+1];
        dp[1]=nums[0];
        int len=1;
        for(int i=1;idp[len]){
                dp[++len]=nums[i];
            }
            else{
                int l=1;
                int r=len;
                while(l> 1;
                    if(nums[i]<=dp[mid]){
                        r=mid;
                    }
                    else{
                        l=mid+1;
                    }
                }
                dp[l]=nums[i];
            }
        }
        return len;

    }
}

  本题运用了两种算法来解决，分别为 动态规划 和 贪心+二分查找。在贪心算法中，我们充分考虑了递增子序列的规律，采用了一种有效的贪心策略来优化算法：我们尽可能让 dp 数组结尾的数小，这样序列就越容易变长。同时，我们采用了二分查找来加速 dp 数组的更新。

  二分查找的框架：

                while(l> 1;
                    
                    if(条件){
                        //更新右边界
                        r=mid;
                    }
                    else{
                        //更新左边界
                        l=mid+1;
                    }