动态规划二分法

难度中等

题目描述

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

• https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

  思路一

  

  思路二

  

  Code

  ```java /**

  • 解法一
  • @param nums

  • @return */ public int lengthOfLIS1(int[] nums) { int len = nums.length; if (len < 2) { return len; } int[] dp = new int[len]; Arrays.fill(dp, 1);

    for (int i = 1; i < len; i++) { for (int j = 0; j < i; j++) {

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

    } }

    int res = 0; for (int i = 0; i < len; i++) { res = Math.max(res, dp[i]); } return res; }

/**

 * 解法二
 * @param nums
 * @return

*/ public int lengthOfLIS2(int[] nums) { int len = nums.length; if (len <= 1) { return len; }

// tail 数组的定义：长度为 i + 1 的上升子序列的末尾最小是几
int[] tail = new int[len];
// 遍历第 1 个数，直接放在有序数组 tail 的开头
tail[0] = nums[0];
// end 表示有序数组 tail 的最后一个已经赋值元素的索引
int end = 0;

for (int i = 1; i < len; i++) {
    // 【逻辑 1】比 tail 数组实际有效的末尾的那个元素还大
    if (nums[i] > tail[end]) {
        // 直接添加在那个元素的后面，所以 end 先加 1
        end++;
        tail[end] = nums[i];
    } else {
        // 使用二分查找法，在有序数组 tail 中
        // 找到第 1 个大于等于 nums[i] 的元素，尝试让那个元素更小
        int left = 0;
        int right = end;
        while (left < right) {
            // 选左中位数不是偶然，而是有原因的，原因请见 LeetCode 第 35 题题解
            // int mid = left + (right - left) / 2;
            int mid = left + ((right - left) >>> 1);
            if (tail[mid] < nums[i]) {
                // 中位数肯定不是要找的数，把它写在分支的前面
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 走到这里是因为 【逻辑 1】 的反面，因此一定能找到第 1 个大于等于 nums[i] 的元素
        // 因此，无需再单独判断
        tail[left] = nums[i];
    }
    // 调试方法
    // printArray(nums[i], tail);
}
// 此时 end 是有序数组 tail 最后一个元素的索引
// 题目要求返回的是长度，因此 +1 后返回
end++;
return end;

} ```