Longest Increasing Subsequence Solutions in C++

// Source : https://leetcode.com/problems/longest-increasing-subsequence/
// Author : Calinescu Valentin, Hao Chen
// Date   : 2015-11-06





// O(n^2) - dynamic programming
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        
        int len = nums.size();
        int maxLen = 0;
        vector<int> dp(len, 1);
        
        for (int i=0; i<len; i++) {
            for(int j=0; j<i; j++) {
                if ( nums[j] < nums[i] ) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};


class Solution {
public:
    
/* 
 * Solution 1 - O(N^2)
 * =========
 *
 * LIS - longest increasing subsequence
 *
 * We iterate through the elements to find the LIS that ends with the current element. 
 * To do that we need to look at all of the previous elements and find one smaller than
 * the current one so that we can add the current one to the sequence terminated in the 
 * smaller one. The length of the LIS ending in the current element is the length of the
 * LIS ending in the smaller one + 1. To find the maximum current LIS we need to use the
 * maximum previous LIS that satisfies the conditions.
 * 
 */
    vector <int> longest_LIS;
    int lengthOfLIS(vector<int>& nums) {
        int answer = 0;
        if(nums.size())
        {   
            longest_LIS.push_back(1);
            answer = 1;
            for(int i = 1; i < nums.size(); i++)
            {
                int maximum = 1;
                for(int j = 0; j < longest_LIS.size(); j++)
                    if(nums[i] > nums[j])
                        maximum = max(maximum, longest_LIS[j] + 1);
                longest_LIS.push_back(maximum);
                answer = max(maximum, answer);
            }
        }
        return answer;
    }
/* 
 * Solution 2 - O(N * logN)
 * =========
 *
 * LIS - longest increasing subsequence
 * 
 * We iterate through the elements to find the position of the current element in the
 * current LIS. After we find its position we change the LIS replacing the next biggest 
 * element with the current one or increase the size of the sequence if the current element
 * is bigger than the biggest one. This way we keep the LIS with the smallest possible
 * elements. By keeping any other LIS we can encounter an element that could have been added
 * to the LIS with the smallest elements, but can't be added to the current one, therefore
 * missing the solution.
 * 
 */
    vector <int> longest_subsequence; // the LIS
    vector <int> nums;
    int binary_search(int number)
    {
        int start = 0, end = longest_subsequence.size() - 1;
        if(start == end)
        {
            if(number > longest_subsequence[start])
                return start + 1;
            else
                return start;
        }
        while(start < end)
        {
            if(start == end - 1)
            {
                if(number > longest_subsequence[start] && number <= longest_subsequence[end])
                    return end;
                else if(number <= longest_subsequence[start])
                    return start;
                else
                    return end + 1;
            }
            int middle = (start + end + 1) / 2;
            if(longest_subsequence[middle] < number)
                start = middle;
            else
                end = middle;
        }
    }
    int lengthOfLIS(vector<int>& nums) {
        int answer = 0;
        if(nums.size())
        {   
            answer = 1;
            longest_subsequence.push_back(nums[0]);
            for(int i = 1; i < nums.size(); i++)
            {
                int position = binary_search(nums[i]);
                if(position == longest_subsequence.size())
                    longest_subsequence.push_back(nums[i]);
                else
                    longest_subsequence[position] = nums[i];
                answer = max(answer, position + 1);
            }
        }
        return answer;
    }
};

/// Source : https://leetcode.com/problems/longest-increasing-subsequence/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>
using namespace std;

/// Memory Search
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

private:
    // memo[i] is the length of the longest increasing sequence end in nums[i]
    vector<int> memo;

    int getMaxLength(const vector<int> &nums, int index){

        if(memo[index] != -1)
            return memo[index];

        int res = 1;
        for(int i = 0 ; i <= index-1 ; i ++)
            if(nums[index] > nums[i])
                res = max(res, 1 + getMaxLength(nums, i));

        memo[index] = res;
        return res;
    }

public:
    int lengthOfLIS(vector<int>& nums) {

        if(nums.size() == 0)
            return 0;

        memo = vector<int>(nums.size(), -1);
        int res = 1;
        for(int i = 0 ; i < nums.size() ; i ++)
            res = max(res, getMaxLength(nums, i));

        return res;
    }
};

int main() {

    int nums1[] = {10, 9, 2, 5, 3, 7, 101, 18};
    vector<int> vec1(nums1, nums1 + sizeof(nums1)/sizeof(int));
    cout << Solution().lengthOfLIS(vec1) << endl;
    // 4

    // ---

    int nums2[] = {4, 10, 4, 3, 8, 9};
    vector<int> vec2(nums2, nums2 + sizeof(nums2)/sizeof(int));
    cout << Solution().lengthOfLIS(vec2) << endl;
    // 3

    // ---

    int nums3[] = {2, 2};
    vector<int> vec3(nums3, nums3 + sizeof(nums3)/sizeof(int));
    cout << Solution().lengthOfLIS(vec3) << endl;
    // 1

    // ---

    int nums4[] = {1, 3, 6, 7, 9, 4, 10, 5, 6};
    vector<int> vec4(nums4, nums4 + sizeof(nums4)/sizeof(int));
    cout << Solution().lengthOfLIS(vec4) << endl;
    // 6

    return 0;
}

/// Source : https://leetcode.com/problems/longest-increasing-subsequence/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>
using namespace std;

/// Dynamic Programming
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

public:
    int lengthOfLIS(vector<int>& nums) {

        if(nums.size() == 0)
            return 0;

        // memo[i] is the length of the longest increasing sequence end in nums[i]
        vector<int> memo(nums.size(), 1);
        for(int i = 1 ; i < nums.size() ; i ++)
            for(int j = 0 ; j < i ; j ++)
                if(nums[i] > nums[j])
                    memo[i] = max(memo[i], 1 + memo[j]);

        int res = memo[0];
        for(int i = 1 ; i < nums.size() ; i ++)
            res = max(res, memo[i]);

        return res;
    }
};

int main() {

    int nums1[] = {10, 9, 2, 5, 3, 7, 101, 18};
    vector<int> vec1(nums1, nums1 + sizeof(nums1)/sizeof(int));
    cout << Solution().lengthOfLIS(vec1) << endl;
    // 4

    // ---

    int nums2[] = {4, 10, 4, 3, 8, 9};
    vector<int> vec2(nums2, nums2 + sizeof(nums2)/sizeof(int));
    cout << Solution().lengthOfLIS(vec2) << endl;
    // 3

    // ---

    int nums3[] = {2, 2};
    vector<int> vec3(nums3, nums3 + sizeof(nums3)/sizeof(int));
    cout << Solution().lengthOfLIS(vec3) << endl;
    // 1

    // ---

    int nums4[] = {1, 3, 6, 7, 9, 4, 10, 5, 6};
    vector<int> vec4(nums4, nums4 + sizeof(nums4)/sizeof(int));
    cout << Solution().lengthOfLIS(vec4) << endl;
    // 6

    return 0;
}int main() {

    int nums1[] = {10, 9, 2, 5, 3, 7, 101, 18};
    vector<int> vec1(nums1, nums1 + sizeof(nums1)/sizeof(int));
    cout << Solution().lengthOfLIS(vec1) << endl;
    // 4

    // ---

    int nums2[] = {4, 10, 4, 3, 8, 9};
    vector<int> vec2(nums2, nums2 + sizeof(nums2)/sizeof(int));
    cout << Solution().lengthOfLIS(vec2) << endl;
    // 3

    // ---

    int nums3[] = {2, 2};
    vector<int> vec3(nums3, nums3 + sizeof(nums3)/sizeof(int));
    cout << Solution().lengthOfLIS(vec3) << endl;
    // 1

    // ---

    int nums4[] = {1, 3, 6, 7, 9, 4, 10, 5, 6};
    vector<int> vec4(nums4, nums4 + sizeof(nums4)/sizeof(int));
    cout << Solution().lengthOfLIS(vec4) << endl;
    // 6

    return 0;
}

/// Source : https://leetcode.com/problems/longest-increasing-subsequence/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Dynamic Programming
/// Best Solution for LIS Problem
///
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution {

public:
    int lengthOfLIS(vector<int>& nums) {

        if(nums.size() == 0)
            return 0;

        // dp[i] is the last num for length i increasing sequence
        vector<int> dp(nums.size() + 1, INT_MIN);
        dp[1] = nums[0];
        int len = 1;
        for(int i = 1 ; i < nums.size() ; i ++) {
            if(nums[i] > dp[len]){
                len ++;
                dp[len] = nums[i];
            }
            else{
                vector<int>::iterator iter = lower_bound(dp.begin(), dp.begin() + (len + 1), nums[i]);
                if(*iter != nums[i]){
                    int index = iter - dp.begin();
                    assert(index >= 1 && index <= len);
                    dp[index] = min(dp[index], nums[i]);
                }
            }
        }

        return len;
    }
};

int main() {

    int nums1[] = {10, 9, 2, 5, 3, 7, 101, 18};
    vector<int> vec1(nums1, nums1 + sizeof(nums1)/sizeof(int));
    cout << Solution().lengthOfLIS(vec1) << endl;
    // 4

    // ---

    int nums2[] = {4, 10, 4, 3, 8, 9};
    vector<int> vec2(nums2, nums2 + sizeof(nums2)/sizeof(int));
    cout << Solution().lengthOfLIS(vec2) << endl;
    // 3

    // ---

    int nums3[] = {2, 2};
    vector<int> vec3(nums3, nums3 + sizeof(nums3)/sizeof(int));
    cout << Solution().lengthOfLIS(vec3) << endl;
    // 1

    // ---

    int nums4[] = {1, 3, 6, 7, 9, 4, 10, 5, 6};
    vector<int> vec4(nums4, nums4 + sizeof(nums4)/sizeof(int));
    cout << Solution().lengthOfLIS(vec4) << endl;
    // 6

    return 0;
}