[LintCode] Longest Increasing Subsequence 最长递增子序列

简介:

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Have you met this question in a real interview?

Example

For [5, 4, 1, 2, 3], the LIS  is [1, 2, 3], return 3

For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

Challenge

Time complexity O(n^2) or O(nlogn)

Clarification

What's the definition of longest increasing subsequence?

    * The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.  

    * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

我们先来看一种类似Brute Force的方法,这种方法会找出所有的递增的子序列,并把它们都保存起来,最后再找出里面最长的那个,时间复杂度为O(n2),参见代码如下:

class Solution {
public:
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> nums) {
        vector<vector<int> > solutions;
        longestIncreasingSubsequence(nums, solutions, 0);
        int res = 0;
        for (auto &a : solutions) {
            res = max(res, (int)a.size());
        }
        return res;
    }
    void longestIncreasingSubsequence(vector<int> &nums, vector<vector<int> > &solutions, int curIdx) {
        if (curIdx >= nums.size() || curIdx < 0) return;
        int cur = nums[curIdx];
        vector<int> best_solution;
        for (int i = 0; i < curIdx; ++i) {
            if (nums[i] <= cur) {
                best_solution = seqWithMaxLength(best_solution, solutions[i]);
            }
        }
        vector<int> new_solution = best_solution;
        new_solution.push_back(cur);
        solutions.push_back(new_solution);
        longestIncreasingSubsequence(nums, solutions, curIdx + 1);
    }
    vector<int> seqWithMaxLength(vector<int> &seq1, vector<int> &seq2) {
        if (seq1.empty()) return seq2;
        if (seq2.empty()) return seq1;
        return seq1.size() < seq2.size() ? seq2 : seq1;
    }  
};

本文转自博客园Grandyang的博客,原文链接:最长递增子序列[LintCode] Longest Increasing Subsequence ,如需转载请自行联系原博主。

相关文章
|
8月前
Leetcode 516. Longest Palindromic Subsequence
找到一个字符串的最长回文子序列,这里注意回文子串和回文序列的区别。子序列不要求连续,子串(substring)是要求连续的。leetcode 5. Longest Palindromic Substring就是求连续子串的。
30 0
LeetCode 376. Wiggle Subsequence
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。
77 0
LeetCode 376. Wiggle Subsequence
|
索引
LeetCode 392. Is Subsequence
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
80 0
LeetCode 392. Is Subsequence
|
算法
LeetCode 300. Longest Increasing Subsequence
给定一个无序的整数数组,找到其中最长上升子序列的长度。
38 0
LeetCode 300. Longest Increasing Subsequence
|
人工智能
POJ 2533 Longest Ordered Subsequence
POJ 2533 Longest Ordered Subsequence
93 0