# 300. Longest Increasing Subsequence

## Design

### Method I (Dynamic Programming)

1. Initialize an array dp for storing the increasing subsequence length for each element inside the array nums, and a variable maxLen for recording the max length of the increasing subsequence to the current element.
2. Traverse through the array nums, for each one, traverse its previous elements. If the previous element is smaller than the current element, update the increasing subsequence length and store it into the array dp.
3. If the variable maxLen is smaller than the longest increasing subsequence length so far, update it.
4. Return maxLen until the end of the loop. ### Method II (Binary Search)

Chinese version: https://segmentfault.com/a/1190000003819886

## Implementation

### Method I

class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int maxLen = 0;
for (int i = 0; i < nums.length; i++) {
int len = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
len = Math.max(len, dp[j] + 1);
}
}
dp[i] = len;
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
}

### Method II

class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int len = 0;
for (int num : nums) {
int left = 0, right = len;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < num)
left = mid + 1;
else
right = mid;
}
tails[left] = num;
if (left == len) ++len;
}
return len;
}
}

## Complexity Analysis

### Method I

Time: $O(n^2)$

Space: $O(n)$

### Method II

Time: $O(nlogn)$

Space: $O(n)$