[LC 300]. Longest Increasing Subsequence

每遇到一个新的数字,可能会需要修改之前算好的结果,所以是典型的dp思路。

Example: nums = [2,5,3,7,101,18]

比较好想的一种解法:int[] dp 存当前subsequence的最大可能长度,初始值所有元素都是1。对于例子来说,dp = [1, 2, 2, 3, 4, 4]。算到 nums[2] = 3 时,3 < 5,略过,3 > 2,dp[2] = max(dp[0] + 1, dp[2]).这种解法需要O(n^2),因为每算一个dp[i],需要比较nums[i] 和 所有nums[0] – nums[i-1]。

另外一种解法improve之前的:int[] dp 存当前subsequence的最大值(即sequence结束的那个值)。每算一个新的dp[i],需要找到nums[i]在当前subsequence的位置。如果位置在subsequence的中间,那么最大长度len不变。如果位置在最末,说明当前subsequence被延长了一个数,len+1. 顺利写出这种解法,最好是了解Arrays.binarySearch()的输入和输出。

类似解法的题目,2D problem:[LC 354]. Russian Doll Envelopes


public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length]; //
    int len = 0;

    for (int x : nums) {
    int i = Arrays.binarySearch(dp, 0, len, x);
    if (i < 0) {
        // can not find x in array, return -insertion_idx-1
        i = -(i+1); // now i is the insertion_idx
    }
    dp[i] = x;
    if (i == len) len++;
}

return len;

}

几个有助于理解这个解法的例子:

[2,3,4,5,1], [2,5,3,7,101,18], [10,9,1,2,3,4]

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s