9.Longest Increasing Subsequence

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Solution I: Dynamic Programming

Using an array to store LIS for each index.

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

        int n = nums.size();

        int i = 0;
        int j = 1;
        vector<int> v(n, 1);

        while (j < n)
        {

            while (i <= j)
            {
                if (nums[i] < nums[j])
                {
                    v[j] = max(v[j], v[i] + 1);
                }

                i++;
            }

            i = 0;
            j = j + 1;
        }

        int max = 0;
        for (int k = 0; k < n; k++)
        {
            if (v[k] > max)
            {
                max = v[k];
            }
        }

        return max;
    }
};

Time Complexity: O(N^2), Space Complexity: O(n)

Solution II: (DP + Binary Search)

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

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

        vector<int> lis;
        lis.push_back(nums[0]);

        for (int i = 1; i < nums.size(); i++)
        {

            int end = lis.size() - 1;

            if (nums[i] > lis[end])
            {
                lis.push_back(nums[i]);
            }
            else
            {
                auto itr = lower_bound(lis.begin(), lis.end(), nums[i]);
                int idx = itr - lis.begin();
                lis[idx] = nums[i];
            }
        }

        return lis.size();
    }
};

Time Complexity: O(n log n)

Lower Bound Implementation

   int lowerBound(vector<int> &v, int target)
    {

        int start = 0;
        int end = v.size();

        while (start < end)
        {
            int mid = (start + end) / 2;
            if (target >= v[mid])
            {
                end = mid;
            }
            else
            {
                start = mid;
            }
        }
        return start;
    }