[leetcode] Longest Increasing Subsequence

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?

分析：这个题目翻译一下：求最长递增子序列长度，注意这里递增序列可以不连续。这是一个经典的动态规划问题。

最经典的一个动态规划做法如下：

1、维持一个dp数组，dp[i]用来保存以i位置元素结尾的最长递增子序列长度；

2、对于边界，当i=0时很容易得出：dp[0]=1；

3、对于状态转移方程，我们假设从0~x-1都已经确定，对于以nums[x]结尾的子串，我们需要遍历0~x-1，比较nums[x]与nums[j]（0<=j<=x-1），在nums[j]<nums[x]的前提下，dp[x]=max{1,dp[j]+1}。

4、注意这里dp保存的一定是以dp[i]结尾的最长递增子序列长度。所以求全部数组最长递增子序列需要将dp数组遍历求最大。

举个例子，对于nums=[1,3,6,7,9,4,10,5,6]，我们要找以第6个位置，也就是nums[6]=10结尾的字串中最长的递增字串长度。

我们假设已经知道dp[0]——dp[5]=[1,2,3,4,5,3],那么对于nums[6]，首先找到nums中所有比10小的数字，j从0——5遍历，发现每个数字都比10小，于是就计算dp[6]=max{1,dp[0]+1,dp[1]+1,...,dp[5]+1}=6。

代码如下：

 1 class Solution {
 2     public int lengthOfLIS(int[] nums) {
 3         if ( nums == null || nums.length == 0 ) return 0;
 4         int[] dp = new int[nums.length];
 5         dp[0]=1;
 6         for ( int i = 1 ; i < nums.length ; i ++ ){
 7             int max_t = 1;
 8             for ( int j = 0 ; j < i ; j ++ ){
 9                 if ( nums[j] < nums[i] ){
10                     max_t = Math.max(max_t,dp[j]+1);
11                 }
12             }
13             dp[i]=max_t;
14         }
15         int res = 0;
16         for ( int i : dp ) {
17             res = Math.max(i,res);
18         }
19         return res;
20     }
21 }

运行时间13ms，击败65.06%。

注意！！！这是最经典的方法啦，不要想着对这个思路进行改进啦。我已经尝试改变dp的含义等等，发现都不可以。因此遇到最长递增子序列，就用这个方法就行啦！！！一定要注意dp数组的含义。

思路二：使用dp+二分查找。时间复杂度o(nlogn)。

1、dp[i]用来存储所有长度为i+1的递增序列中，末尾最小的元素的值；（所以dp数组一定是递增的！）

2、边界情况dp[0]=min{nums}，因此不需用单独拿出来讨论；

3、状态转移方程，对于x位置，假设dp[0]——dp[x-1]都已知。有两种情况：第一种，nums[x]比dp[x-1]大，那么dp[x] = nums[x]，并且size++；第二种，dp[k]<nums[x]<=dp[k+1]，dp[k]=nums[x]。

代码如下：

 1 class Solution {
 2     public int lengthOfLIS(int[] nums) {
 3         int[] dp = new int[nums.length];
 4         int len = 0;
 5         for ( int num : nums ){
 6             int i = 0;
 7             int j = len;
 8             while ( i < j ){
 9                 int mid = ( i + j ) / 2;
10                 if ( dp[mid] < num ){
11                     i = mid + 1;
12                 }else {
13                     j = mid  ;
14                 }
15             }
16             dp[i] = num;
17             if ( i == len ) len++;
18         }
19         return len;
20     }
21 }

运行时间1ms。

[leetcode] Longest Increasing Subsequence

相关推荐