[LeetCode] 300. Longest Increasing Subsequence

本文主要是介绍[LeetCode] 300. Longest Increasing Subsequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/longest-increasing-subsequence/description/

题目

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

题目大意

找nums数值中，最长的升序字串，输出其长度。

思路

方法一

动态规划 O(n²)

状态dp[i]：以 nums[n] 结尾的序列的最长递增子序列长度。

状态转移方程：
dp[i] = max(1, dp[p] + 1 )，其中 i>p 且 nums[i] > nums[p];

若下标 p < i，且 nums[p] < nums[i] ，也就是，从下标 i处，看前面比nums[i] 小的元素作为结尾的最长升序串L。由于 L存在多个，所以可以选取最大的L。

在遍历时候，从i-1 向前遍历，若当前下标 j +1> 当前最大tmaxL，继续比较下标j的元素，否则不用继续比较。因为此时 tmaxL 已经大于前面元素的个数和，子串长度不可能大于tmaxL。

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

由于 tsubmaxlen >=0 所以 j>=0 &&j+1>tsubmaxlen 可简化为 j>=tsubmaxlen。

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

方法二

动态规划 O(n log n)

状态tails[i]：存储长度为 i + 1 的最长递增子序列的最后一个元素。

状态转移：

对于一个元素 x，

如果它大于 tails 数组所有的值，那么把它添加到 tails 后面，表示最长递增子序列长度加 1；
如果 tails[i-1] < x <= tails[i]，那么更新 tails[i] = x。

其实就是求他的一个 lower_bound 。

例如对于数组 [4,3,6,5]，有：

tails      len      num
[]         0        4
[4]        1        3
[3]        1        6
[3,6]      2        5
[3,5]      2        null

可以看出 tails 数组保持有序，因此在查找 S_i 位于 tails 数组的位置时就可以使用二分查找。

class Solution {public int binarySearch(int []tails,int len,int key){int l = 0,h = len-1;while(l<=h){int m = l + (h - l)/2;if(tails[m] > key){h = m -1;}else if(tails[m] < key){l = m + 1;}else    return m;}return l;}public int lengthOfLIS(int[] nums) {int[] tails = new int[nums.length];int len = 0;for(int i = 0 ;i < nums.length; i++){int index = binarySearch(tails,len,nums[i]);tails[index] = nums[i];if(index == len) len++;}return len;}
}

更简洁的写法

class Solution {public int lowerBound(int[] nums,int l ,int r,int target){while(l<r){int m = (l + r) /2;if(nums[m] < target)l =  m + 1;elser = m;}return l;}public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];int size = 0;for(int num : nums){int pos = lowerBound(dp,0,size,num);dp[pos] = num;if(pos == size)size++;}return size;}
}