1. //给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 
  2. //
  3. // 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序
  4. //列。 
  5. // 
  6. //
  7. // 示例 1： 
  8. //
  9. // 
  10. //输入：nums = [10,9,2,5,3,7,101,18]
  11. //输出：4
  12. //解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
  13. // 
  14. //
  15. // 示例 2： 
  16. //
  17. // 
  18. //输入：nums = [0,1,0,3,2,3]
  19. //输出：4
  20. // 
  21. //
  22. // 示例 3： 
  23. //
  24. // 
  25. //输入：nums = [7,7,7,7,7,7,7]
  26. //输出：1
  27. // 
  28. //
  29. // 
  30. //
  31. // 提示： 
  32. //
  33. // 
  34. // 1 <= nums.length <= 2500 
  35. // -104 <= nums[i] <= 104 
  36. // 
  37. //
  38. // 
  39. //
  40. // 进阶： 
  41. //
  42. // 
  43. // 你可以设计时间复杂度为 O(n2) 的解决方案吗？ 
  44. // 你能将算法的时间复杂度降低到 O(n log(n)) 吗? 
  45. // 
  46. // Related Topics 二分查找 动态规划 
  47. // 👍 1366 👎 0

这题其实挺复杂的，要求递增子序列 [491]递增子序列，而且要最长递增子序列。
那么如果昨晚491题，直接找出最长的长度即可。
那么491题的时间复杂度为 O(2 n),再选择出最长的长度，就是O(2 n )。这个复杂度显然有些过高。
那么重新看题，题目要求返回最长严格递增子序列的 长度 。
只要求长度，不需要找到具体的子序列。

一 dp

子序列要求的是顺序固定，不一定重复， 那么使用动态规划的做法，dp数组保存的是以i位置结尾，最长的递增子序列长度，且i必须在子序列中。
因为这样就可以只判断结束的数来确定整个递增子序列的最大值，如果nums[cur]大于nums[i]，dp[cur] = dp[i]+1。这就代表将cur和i为结尾的递增子序列组成一个新的，长度+1的递增子序列。

  1. class Solution {
  3.     public int lengthOfLIS(int[] nums) {
  4.         // 如果数组都没有数字，就不存在递增子序列，直接返回0
  5.         if (nums.length == 0) {
  6.             return 0;
  7.         }
  8.         // dp数组，表达以i结尾的递增子序列长度
  9.         int[] dp = new int[nums.length];
  10.         // 只有一个数的时候，他自己就是递增的
  11.         dp[0] = 1;
  12.         int res = 1;
  13.         for (int i = 1; i < nums.length; i++) {
  14.             dp[i] = 1;
  15.             // 依次从i前面找
  16.             for (int j = 0; j < i; j++) {
  17.                 // 找到小于当前数的位置，就可以和当前位置组成一个长度+1的递增子序列
  18.                 if (nums[i] > nums[j]) {
  19.                     dp[i] = Math.max(dp[j] + 1, dp[i]);
  20.                 }
  21.             }
  22.             res = Math.max(res, dp[i]);
  23.         }
  24.         return res;
  25.     }
  26. }

二 贪心

如果我们想要让递增子序列尽量的长，那么就需要使子序列中的数尽量的小。
比如[0,1,2,4,3] 可以找出两个递增子序列，[0,1,2,4]和[0,1,2,3]。
那么如果选择小的那个，当最后再新增一个数字4的时候，就可以组成一个长度为5的递增子序列，而大的那个无法组成更长的递增子序列。
使用一个数组d来保存i长度的递增子序列最后一个数字。
那么如何让子序列中的数字尽量小呢？
因为d保存的是递增子序列的最后一个数字，不同长度的子序列最后一位必然是递增的，因此d是一个单调递增的趋势。
举个例子 [0,3,12,2]， 这个数组，他对应的d数组是[0,2,12], [0,2,12]显然不是一个递增子数组，因为顺序已经发生了改变。但是表达的意思是，长度为1的递增子序列最小值是0， 长度为2的递增子序列最小值是2，长度为3递增子序列最小值是12
因此对应的做法就是，拿到i位置后，看是否可以和当前最长子序列组成一个更长的子序列。
如果可以，将数放到长度+1位置，如果不行，看看找到一个位置使得某个子序列的最后一个值更小。

  1. class Solution {
  3.     public int lengthOfLIS(int[] nums) {
  4.         // len表示当前递增子序列的长度
  5.         int len = 1;
  6.         int n = nums.length;
  7.         if (n == 0) {
  8.             return 0;
  9.         }
  10.         // d表示长度为i的递增子序列末尾最小值
  11.         int[] d = new int[n + 1];
  12.         d[len] = nums[0];
  13.         for (int i = 1; i < n; i++) {
  14.             // 如果当前数字大于最长递增子序列的最大值的话，代表可以组成一个更长的递增子序列
  15.             if (nums[i] > d[len]) {
  16.                 len ++;
  17.                 // 增加长度，并且将当前数放到增加后的位置
  18.                 d[len] = nums[i];
  19.             }else {
  20.                 // 判断是否有可以更新末尾最小值的长度
  21.                 int left = 1;
  22.                 int right = len;
  23.                 // 如果pos是0的话，说明比当前所有的都小，更新第一个位置
  24.                 int pos = 0;
  25.                 // 因为d是单调递增的，可以用二分查找应该更新哪个位置。
  26.                 while (left <= right) {
  27.                     int mid = (left + right) / 2;
  28.                     if (d[mid] < nums[i]) {
  29.                         pos = mid;
  30.                         left = mid + 1;
  31.                     }else {
  32.                         right = mid - 1;
  33.                     }
  34.                 }
  35.                 d[pos + 1] = nums[i];
  36.             }
  37.         }
  38.         return len;
  39.     }
  40. }