## 300. Longest Increasing Subsequence

###### tags: `Dynamic Programming` `Medium`

>[300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/description/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

:::

<hr/>

### Sol
:::spoiler Code

:::

<hr/>

### 東

:::spoiler Code

// Time O(n^2) | Space O(n) - n is the length of nums
var lengthOfLIS = function(nums) {
    const dp = new Array(nums.length).fill(1);

    for (let start = nums.length - 2; start >= 0; start--) {
        for (let second = start + 1; second < nums.length; second++) {
            if (nums[start] < nums[second] && dp[start] < 1 + dp[second]) {
                dp[start] = 1 + dp[second];
            }
        }
    }
    return Math.max(...dp);      
};

:::

<hr/>

### Jessie

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

:::

<hr/>

### Haoyu

:::spoiler Code

#### Try 1: Dynamic Programming

var lengthOfLIS = function(nums) {
    const dp = new Array(nums.length).fill(1);

    for (let i = 0; i < nums.length; i += 1) {
        for (let j = 0; j < i; j += 1) {
            if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }

    return Math.max(...dp);
};


nums = [4,10,4,3,8,9] // 3
nums = [1,3,6,7,9,4,10,5,6] // 6

#### Try 2: Binary Search

var lengthOfLIS = function(nums) {
    const helper = (array, target) => {
        let [start, end] = [0, array.length - 1];

        while (start < end) {
            let mid = Math.floor((start + end) / 2);

            if (array[mid] < target) start = mid + 1;
            else end = mid;
        }

        return start;
    };

    const arr = new Array(nums.length).fill(Number.POSITIVE_INFINITY);

    for (let i = 0; i < nums.length; i += 1) {
        const j = helper(arr, nums[i]);

        arr[j] = nums[i];
    }

    return arr.filter(v => v !== Number.POSITIVE_INFINITY).length;
};

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::