# 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();
}
};