# 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of 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

Approach 1: DP -- O(N^2).

Approach 2: greedy + binary search -- O(NlogN). Keep a table such that table[i-1] contains the smallest number for an increasing subsequence of length i. For each incoming num, do a binary search to insert the num at the proper place (see the patience game: https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf)

# Code (Python)

Approach 1:

    def lengthOfLIS(self, nums: List[int]) -> int:
        # O(N^2) -- DP
        if not nums:
            return 0
        lis = [1 for _ in range(len(nums))]
        for i in range(1, len(lis)):
            for j in range(i):
                if nums[j] < nums[i]:
                    lis[i] = max(lis[i], lis[j] + 1)
        return max(lis)

Approach 2:

    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        piles = [nums[0]]
        for i in range(1, len(nums)):
            # bisect_left()
            left, right = 0, len(piles)
            while left < right:
                mid = (left + right) // 2
                if nums[i] <= piles[mid]:
                    right = mid
                else:
                    left = mid + 1
            if left == len(piles):
                piles.append(nums[i])
            else:
                piles[left] = nums[i]
        return len(piles)

# Code (C++)

Approach 1:

/*
// DP - for element i, calculate the longest increasing subsequence ended with i.
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        int len[n];
        int res = 0;
        for (int i = 0; i < n; ++i)
        {
            len[i] = 1;
            for (int j = 0; j < i; ++j)
            {
                if (nums[j] < nums[i] && len[j] + 1 > len[i])
                    len[i] = len[j] + 1;
            }
            if (len[i] > res)
                res = len[i];
        }
        return res;
    }
};

Approach 2:

/ DP + binary search
// example: {1,2,4,5,3,7,6,4,3}
// table index: 0 1 2 3 4
// table value:
//              1 2 4 5
//              1 2 3 5 7
//              1 2 3 5 6
//              1 2 3 4 6
//              1 2 3 4 6
// Note that the final table may not be the longest increasing subsequence, but its length is.
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> buf;
        for (int i = 0; i < n; ++i)
        {
            int lo = 0;
            int hi = buf.size() - 1;
            while (lo <= hi)
            {
                int mid = lo + (hi - lo) / 2;
                if (nums[i] < buf[mid])
                    hi = mid - 1;
                else if (nums[i] > buf[mid])
                    lo = mid + 1;
                else
                    break;
            }
            if (lo >= buf.size())
                buf.push_back(nums[i]);
            else if (lo > hi)
                buf[lo] = nums[i];
        }
        return buf.size();
    }
};