[LeetCode] Longest Increasing Subsequence

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

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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:动态规划O(n2)。i为递增子序列的末尾元素的位置,依次遍历i之前的位置,更新其值。
思路2:动态规划+二分搜索O(nlgn)。用一个附加数组保存递增序列的尾元素,依次遍历原数组中的元素,将其插入到附加数组中的正确位置,若插入最后一个元素之后,则更新最长递增子序列的长度。

实现代码

C++动态规划法实现代码如下:

// Runtime: 132ms
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0)
        {
            return 0;
        }
        vector<int> cnt(nums.size(), 1);
        int res = 1;
        for (int i = 1; i < nums.size(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i] && cnt[j] + 1 > cnt[i])
                {
                    cnt[i] = cnt[j] + 1;
                    res = max(res, cnt[i]);
                }
            }
        }

        return res;
    }
};

C++动态规划+二分法实现代码:

// Runtime: 4ms
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0)
        {
            return 0;
        }
        vector<int> tail(nums.size(), 0);
        tail[0] = nums[0];
        int len = 1;
        for (int i = 1; i < nums.size(); i++)
        {
            int left = 0;
            int right = len - 1;
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (tail[mid] < nums[i])
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
            tail[left] = nums[i];
            if (left >= len)
            {
                len++;
            }
        }
        return len;
    }
};

java实现代码:

//Runtime: 2 ms
public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int tail[] = new int[nums.length];
        tail[0] = nums[0];
        int len = 1;
        for (int i = 0; i < nums.length; i++) {
            int left = 0;
            int right = len - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (tail[mid] < nums[i]) {
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }
            tail[left] = nums[i];
            if (left == len) {
                ++len;
            }
        }

        return len;
    }
}
时间: 2024-10-27 22:38:53

[LeetCode] Longest Increasing Subsequence的相关文章

[LeetCode] Number of Longest Increasing Subsequence 最长递增序列的个数

Given an unsorted array of integers, find the number of longest increasing subsequence. Example 1: Input: [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7]. Example 2: Input: [2,2,2,2,2] Outpu

[算法]-Longest Increasing Subsequence

看微软笔试题遇到的. Longest Increasing Subsequence(LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keeps increasing.For example, LIS of {2,1,4,2,3,7,4,6} is {1,2,3,4,6}, and its LIS length is 5.

[LeetCode] Longest Continuous Increasing Subsequence 最长连续递增序列

Given an unsorted array of integers, find the length of longest continuous increasing subsequence. Example 1: Input: [1,3,5,4,7] Output: 3 Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] i

UVa 10405:Longest Common Subsequence,最长公共子序列模板题

[链接] http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1346 [原题] Problem C: Longest Common Subsequence Sequence 1: Sequence 2: Given two sequences of characters, print the length of

UVa 10405 Longest Common Subsequence (DP&amp;amp;LCS)

10405 - Longest Common Subsequence Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1346 Sequence 1: Sequence 2: Given two sequences of characters, print

LCS (Longest Common Subsequence) 字符串最长公共子串算法

LCS (Longest Common Subsequence) 算法用于找出两个字符串最长公共子串. 算法原理: (1) 将两个字符串分别以行和列组成矩阵.(2) 计算每个节点行列字符是否相同,如相同则为 1.(3) 通过找出值为 1 的最长对角线即可得到最长公共子串. 人 民 共 和 时 代中 0, 0, 0, 0, 0, 0华 0, 0, 0, 0, 0, 0人 1, 0, 0, 0, 0, 0民 0, 1, 0, 0, 0, 0共 0, 0, 1, 0, 0, 0和 0, 0, 0, 1

POJ 2533 Longest Ordered Subsequence

Description A numeric sequence of ai is ordered if a1 < a2 < - < aN. Let the subsequence of the given numeric sequence (a1, a2, -, aN) be any sequence (ai1, ai2, -, aiK), where 1 <= i1 < i2 < - < iK <= N. For example, sequence (1,

[LeetCode] Monotone Increasing Digits 单调递增数字

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits. (Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)   Exa

[LeetCode] Longest Word in Dictionary 字典中的最长单词

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest l