# 300. Longest Increasing Subsequence (Medium)

https://leetcode.com/problems/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`. ```

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

## Solutions

### 1.

``````class Solution {

// This solution is a much easier one to understand. The key idea is to make use of dynamic programming.

public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int len = nums.length;

int[] track = new int[len + 1];
Arrays.fill(track, 1);

for (int i = len - 1; i >= 0; i--) {

// for ith element, pick the proper subsequent element from (i+1)th to (len-1)th
for (int j = i + 1; j < len; j++) {

// see if meet the condition that requires increasing order
if (nums[i] >= nums[j]) {
continue;
}

track[i] = Math.max(track[i], track[j] + 1);
}
}

int max = 0;
for (int i = 0; i < len; i++) {
max = Math.max(max, track[i]);
}

return max;
}
}
``````

### 2.

``````class Solution {

// This solution is a little bit tedious and trivial. It's strongly advised to adopt the
// Solution instead of this one.

public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int len = nums.length;

int[] track = new int[len+1];
Arrays.fill(track, 0);

recurse(nums, 0, track);

int max = 0;
for (int i = 0; i < len; i++) {
max = Math.max(max, track[i]);
}

return max;
}

private int recurse(int[] nums, int depth, int[] track) {
int len = nums.length;

if (depth >= len) {
return 0;
}

if (track[depth] > 0) {
return track[depth];
}

int max = 1;
for (int i = depth + 1; i < len; i++) {
int rst = recurse(nums, i, track);

// Do not place following condition statements in front of recurse. Otherwise
// it only search for best subset that contains nums[0]
if (nums[depth] >= nums[i]) {
continue;
}

max = Math.max(max, rst + 1);
}

track[depth] = max;

return max;
}
}
``````