题目描述

给你一个整数数组 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 。

示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：
你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

题解

动态规划

len[i]表示以nums[i]为尾元素的递增子序列的最大长度。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[]len=new int[nums.length];

        int max=1;
        for(int i=0;i<nums.length;++i){
            len[i]=1;
            for(int j=0;j<i;++j){
                if(nums[i]>nums[j]&&len[j]+1>len[i]){
                    len[i]=len[j]+1;
                    if(max<len[i]){
                        max=len[i];
                    }
                }
            }
        }
        return max;
    }
}

贪心+动态规划+二分查找（参考官方题解）

  • 贪心：对于相同长度的递增子序列而言，尾元素越小，后续元素组成递增子序列的可能性越高。

tail[i]表示长度为i+1的递增子序列尾元素的最小值a。因为长度为i+2的递增子序列的尾元素大于其倒数第二个元素b，且b大于等于a，因此tail[i+1]>tail[i]，即tail数组是严格递增的。因此tail数组的更新规则如下：

  • 如果nums[i]>tail数组最后一个元素，则将nums[i]加入tail数组尾部，即递增子序列长度+1。

  • 如果nums[i]<=tail数组最后一个元素，则二分查找tail数组，将大于nums[i]的最小元素替换为nums[i]，即对应长度的递增子序列的尾元素变小。

    class Solution {
  public int lengthOfLIS(int[] nums) {
      int[] tail=new int[nums.length];
      int len=0;

      // 只有一个元素时，递增子序列长度为1
      tail[len++]=nums[0];

      for(int i=1;i<nums.length;++i){
          // 大元素直接加入序列尾部
          if(nums[i]>tail[len-1]){
              tail[len++]=nums[i];
          }else{
              int left=0,right=len-1;
              // 左小右大的元素
              while(left<right){
                  int mid=(left+right)/2;
                  if(tail[mid]<nums[i]){
                      left=mid+1;
                  }else{
                      right=mid;
                  }
              }
              tail[left]=nums[i];
          }
      }
      return len;
  }
}