Longest Increasing Sub sequence

Description

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

You code should return the length of the LIS.

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. wiki LIS

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 [2, 4, 5, 7], return 4

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

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

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
        if (nums.empty()) {
            return 0;
        }
        int n = nums.size();
        vector<int> dp;
        for (int i = 0; i < n; ++i) {
            int index = binsearch(dp, nums[i]);
            if (index == dp.size()) {
                dp.push_back(nums[i]);
            } else {
                dp[index] = nums[i];
            }
        }
        return dp.size();
        // // Or we can
        // // test nums[i] > dp.back() ?
        // // if so, push_back() directly
        // // if not, binary search to find the first index larger than nums[i]
        // dp.push_back(nums[0]);
        // for (int i = 1; i < n; ++i) {
        //     if (nums[i] >= dp.back()) {
        //         dp.push_back(nums[i]);
        //     } else {
        //         int index = binsearch(dp, nums[i]);
        //         dp[index] = nums[i];
        //     }
        // }
        // return dp.size();
    }
private:
    int binsearch(vector<int>& nums, int target) {
        if (nums.empty()) {
            return 0;
        }
        int start = 0;
        int end = nums.size()-1;
        while (start+1 < end) {
            int mid = start + (end-start)/2;
            if (target >= nums[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        // ---------------------------------------------------------------
        // also ok for lintcode 
        // 
        // if (target <= nums[start]) {
        //     return start;
        // } else {// if (target < nums[end]) {
        //     return end;
        // }
        // return nums.size();
        // ----------------------------------------------------------------
        // for allowed duplicate, we find the first num, that exceeding the target
        // that is for lintcode, test case 1,1,1, desired answer 3
        // if (target < nums[start]) {
        //     return start;
        // } else if (target < nums[end]) {
        //     return end;
        // }
        // return nums.size();
        // ----------------------------------------------------------------
        // for not allowed duplicate, we find the first match.
        // that is for leetcode, test case 1,1,1, desired answer 1
        if (target <= nums[start]) {
            return start;
        } else if (target <= nums[end]){
            return end;
        }
        return nums.size();
    }
};

Similar problems

x

Tags

x