300.最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

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

1. 动规。从前往后遍历，dp[i]表示以nums[i]为最右端的最长子序列长度，遍历j从0到i-1更新dp[i]时，if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);这里要理解的是，更新dp[i]过程中要找的是最长子序列中nums[i]的前驱节点，然后判断以该前驱节点为右端点的长度加1是否比dp[i]大，而不是从头开始一个个找串起来，这样想的话就和动规没什么关系了。

   反过来也可以从后往前遍历，每次遍历找到比nums[i]大的nums[j]，并判断nums[j]有没有资格作为nums[i]的直接后继。时间复杂度为O(n^2)

    for(int i=0;i<nums.length;i++)
    for(int j=0;j<=i-1;j++)
     {
         if(nums[j]<nums[i])
         {
             dp[i]=Math.max(dp[i],dp[j]+1);
             max=Math.max(max,dp[i]);
         }
     }
   

2. 贪心+二分法。算法非常巧妙比较难想。设置一个数组d[]保存序列和len标记最长序列长度。数组d[]的更新分两种情况:

   • 如果nums[i]大于d数组最大元素d[len]，则令nums[i]插入d[len]后面一个位置。
   • 如果nums[i]小于d数组最大元素，则把nums[i]放入d数组中第一个比nums[i]大的元素的位置。

   首先d数组的保存的值一定是递增的，因为d数组的更新规则都没有破坏它的有序性，这点很重要，d数组有序才可以用二分法。而对于上面第二点，d数组保存的不一定是子序列。原因有两点，第一更新到d中并没有改变len值(不是插入)，对结果没有影响。第二这样子做是能够考虑到1,100,20,30的情况，体现了贪心的思想，相同长度相同位置下把更小的数替换到d中。实际上，d[i]的含义是在整个nums数组中子序列长度为i时的最小末尾元素的值。

   第二个问题，d[len]存在为什么能保证一定存在长度为len的子序列，因为d[0]~ d[len-1]保存的并不一定是子序列。数组是前往后遍历的，因此赋值(插入)到d[len]位置的第一个元素(在刚赋值的那个时间点)在nums数组中一定是出现在d[0]~d[len-1]元素之前的，也就是说如果存在长度为len-1的子序列，那么这个第一个插入到len位置的元素d[len]就可以加入其中，插入到len-1子序列末尾，构成长度为len的子序列。根据数学归纳法就可以得出，len子序列是一定存在的。

   数组d更新时，遇到第二种情况，就可以用二分法找到替换位置。时间复杂度为O(nlogn)。

    public int lengthOfLIS(int[] nums) {
          int len=0;
          int[] d=new int[nums.length];
          d[0]=nums[0];
          for(int i=1;i<nums.length;i++)
          {
              if(nums[i]>d[len])
              {
                  len++;
                  d[len]=nums[i];
              }
              else
              {
                  int low=0,high=len;
                  while(low<high)
                  {
                      int mid=(low+high)/2;
                      if(d[mid]<nums[i])
                      low=mid+1;
                      else
                      high=mid;
                  }
                  d[low]=nums[i];
              }
          }
          return len+1;
      }
   

1671. 得到山形数组的最少删除次数 (opens new window)

1、前后缀+最长递增子序列

计算以每个索引下标为山峰时，前后子数组的最少删除字数。而子数组的最少删除字数的求解过程即为“最长递增子序列”。

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int[] prefix = new int[nums.length];
        int[] suffix = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            prefix[i] = 1;
            for (int j = 0; j < i; j++) {
                if(nums[i]>nums[j]) prefix[i] = Math.max(prefix[i], prefix[j] + 1);
            }
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            suffix[i]=1;
            for (int j = nums.length - 1; j > i; j--) {
                if(nums[i]>nums[j]) suffix[i] = Math.max(suffix[i], suffix[j] + 1);
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if(suffix[i]!=1&&prefix[i]!=1){
                res = Math.min(res, nums.length - (suffix[i] + prefix[i] - 1));
            }
            
        }
        return res;
    }
}