Longest Increasing Subsequence

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

You code should return the length of the LIS.

http://www.lintcode.com/en/problem/longest-increasing-subsequence/

Discussion

动归解法。状态f[i]表示一nums[i]结尾的LIS的长度，状态转移方程为：$$f[i] = max(f[j]+1)$$, where $$0<=j<i, nums[j]<=nums[i]$$. 结果是f[i]中最大的那个。

Solution

class Solution {
public:
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> nums) {
        // write your code here
        int n = nums.size();
        if(n==0) return 0;
        int result = 0;
        vector<int> f(n,0);
        f[0] = 1;
        for(int i=1; i<n; i++) {
            f[i] = 1;
            for(int j=0; j<i; j++) {
                if(nums[j] <= nums[i]) {
                    f[i] = max(f[i], f[j]+1);
                }
            }
            result = max(result, f[i]);
        }
        return result;
    }
};

O(n^2) runtime, O(n) space.

还有o(logn)的解法，TBD

// Time:  O(nlogn)
// Space: O(n)

// Binary search solution with STL.
class Solution {
public:
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> nums) {
        vector<int> LIS;

        for (const auto& i : nums) {
            insert(&LIS, i);
        }

        return LIS.size();
    }

private:
    void insert(vector<int> *LIS, const int target) {
        // Find the first index "left" which satisfies LIS[left] > target
        auto it = upper_bound(LIS->begin(), LIS->end(), target);

        // If not found, append the target.
        if (it == LIS->end()) {
            LIS->emplace_back(target);
        } else {
            *it = target;
        }
    }
};

// Binary search solution.
class Solution2 {
public:
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> nums) {
        vector<int> LIS;

        for (const auto& i : nums) {
            insert(&LIS, i);
        }

        return LIS.size();
    }

private:
    void insert(vector<int> *LIS, const int target) {
        int left = 0, right = LIS->size() - 1;
        auto comp = [](int x, int target) { return x > target; };

        // Find the first index "left" which satisfies LIS[left] > target
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (comp((*LIS)[mid], target)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // If not found, append the target.
        if (left == LIS->size()) {
            LIS->emplace_back(target);
        } else {
            (*LIS)[left] = target;
        }
    }
};