# 300. Longest Increasing Subsequence

### Leetcode

<https://leetcode.com/problems/longest-increasing-subsequence/>

### 題目

\
Given an integer array `nums`, return the length of the longest strictly increasing subsequence.

A **subsequence** is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, `[3,6,2,7]` is a subsequence of the array `[0,3,1,6,2,2,7]`.

&#x20;

**Example 1:**

```
Input: nums = [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.
```

**Example 2:**

```
Input: nums = [0,1,0,3,2,3]
Output: 4
```

**Example 3:**

```
Input: nums = [7,7,7,7,7,7,7]
Output: 1
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一 - 動態規劃法**

`dp[i]` 代表在 `index` 為 `i` 時，最長的子序列長度，但要怎麼求出 `dp[i]` 的數值呢？我們可以比較 `nums[i]` 跟之前 `index` 為 `j` 時數字的大小 (即比較 `nums[i]` 與 `nums[j]`)，如果 `nums[i]` 的值比較大的話，就代表 `dp[i]` 可能的值為 `dp[j] + 1` (這裡多加的長度 1 是因為 `nums[i]` 大於 `nums[j]`)

例如：`nums = [1, 7, 3, 4, 10, 5], 此時的 i = 3, nums[i] = 4`

這時我們要做的是遍歷 `i` 之前的數組：

* `j = 0, nums[j] = 1 < nums[i]`

  所以 `dp[4]` 其中一個的可能值為 `dp[0] + 1`，`dp[0]` 前面會算過等於 `1`

  \=> `dp[4] = 1 + 1 = 2`，子字串為 `[1, 4]`
* `j = 1, nums[j] = 7 > nums[i]`

  因為 `nums[i]` 沒有比 `nums[j]` 大，所以 `dp[4]` 其中一個的可能值只有自己

  \=> `dp[4] = 1`，子字串為 `[4]`
* `j = 2, nums[j] = 3 < nums[i]`

  所以 `dp[4]` 其中一個的可能值為 `dp[2] + 1`，`dp[2]` 前面會算過等於 `2`

  \=> `dp[4] = 2 + 1 = 3`，子字串為 `[1, 3, 4]`

接著在每一輪的遍歷中找到這些 **可能性的最大值 dp\[i]**，就是題目要求的答案

```javascript
var lengthOfLIS = function (nums) {
    // 初始化所有 index 時，將最長的子字串預設為 1
    const dp = Array.from(Array(nums.length), () => 1);

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            // 遍歷小於 len 的值，只要目前值大於 index 為 i 時的值，dp[i] = dp[j] + 1
            const newValue = nums[i] > nums[j] ? dp[j] + 1 : 1;
            dp[i] = Math.max(dp[i], newValue);
        }
    }

    // 最後求出所有 dp 中的最大值
    return Math.max(...dp);
};
```

Runtime: 144 ms, faster than 73.96% of JavaScript online submissions for Longest Increasing Subsequence.

Memory Usage: 40.8 MB, less than 26.51% of JavaScript online submissions for Longest Increasing Subsequence.

**Time complexity: 1+2+3+...+n = n(n+1)/2 => O(n^2)**

**Space complexity: the size of `dp` = O(n)**

**參考資料**

{% embed url="<https://leetcode.wang/leetcode-300-Longest-Increasing-Subsequence.html>" %}

* **方法二**

這個方法有點不太直覺，下面我們直接用範例來看一下：

範例：`nums = [3, 5, 6, 2, 4]`

一開始先定義 `arr = [nums[0]]`，這個 `arr` 矩陣紀錄的是 **最長子序列**

* `i = 1, nums[1] = 5`

  因為 `nums[1]` 大於 `arr[0]`，直接加進矩陣後面

  \=> `arr = [3, 5]`
* `i = 2, nums[2] = 6`

  因為 `nums[2]` 大於 `arr[1]`，直接加進矩陣後面

  \=> `arr = [3, 5, 6]`
* `i = 3, nums[3] = 2`

  因為 `nums[3]` 小於 `arr[1]`，需要尋找矩陣中 **剛好大於目前數字的元素(3)** 並替換掉&#x20;

  \=> `arr = [2, 5, 6]`

  (可以發現此時實際的最長子序列應該是 `[3, 5, 6]`，但因為題目只需要求得長度，所以即使紀錄的是`[2, 5, 6]`也沒有關係)
* `i = 4, nums[4] = 4`

  因為 `nums[4]` 小於 `arr[2]`，需要尋找矩陣中 **剛好大於目前數字的元素(5)** 並替換掉&#x20;

  \=> `arr = [2, 4, 6]`

按照上面的邏輯算完後 `arr = [2, 4, 6]`，對應到實際上的最長子序列應該是 `[3, 5, 6]`，但因為答案只需求得 **最長子序列的長度**，所以計算 `arr.length = 3` 就可以了

```javascript
var lengthOfLIS = function (nums) {
    const arr = [nums[0]];

    for (let i = 1; i < nums.length; i++) {
        const value = nums[i];
        // 如果目前數字大於 arr 中最大的數字，即代表最長的子字串可以加 1
        if (value > arr[arr.length - 1]) {
            arr.push(value);
        } else {
            // 尋找 arr 矩陣中剛好大於目前數字的元素，並替換掉它
            for (let j = 0; j < arr.length; j++) {
                if (value <= arr[j]) {
                    arr.splice(j, 1, value);
                    break;
                }
            }
        }
    }

    return arr.length;
};
```

Runtime: 132 ms, faster than 78.47% of JavaScript online submissions for Longest Increasing Subsequence.

Memory Usage: 40.4 MB, less than 65.98% of JavaScript online submissions for Longest Increasing Subsequence.

**Time complexity: O(n^2)** - in the worst case

**Space complexity: O(n)**

**參考資料**

{% embed url="<https://liweiwei1419.github.io/leetcode-solution/leetcode-0300-longest-increasing-subsequence/>" %}

* **方法三**

在方法二中，**尋找 arr 矩陣中剛好大於目前數字的元素，並替換掉它** => 這一步驟是從頭開始遍歷 `arr`矩陣找到這個元素的，但剛好 `arr` 是從小到大已經排序過的矩陣，所以要找出其中 **剛好大於目前數字的元素**，最快的方式就是使用 binary search

```javascript
var lengthOfLIS = function (nums) {
    const arr = [nums[0]];

    for (let i = 1; i < nums.length; i++) {
        const value = nums[i];
        if (value > arr[arr.length - 1]) {
            arr.push(value);
        } else {
            // 利用 binary search 找出剛好大於目前數字的元素
            let low = 0;
            let high = arr.length - 1;

            while (low < high) {
                const mid = Math.floor((low + high) / 2);
                if (value <= arr[mid]) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            arr.splice(low, 1, value);
        }
    }

    return arr.length;
};
```

Runtime: 122 ms, faster than 79.87% of JavaScript online submissions for Longest Increasing Subsequence.

Memory Usage: 40.1 MB, less than 89.37% of JavaScript online submissions for Longest Increasing Subsequence.

**Time complexity: O(n⋅log(n))**

N - 先遍歷矩陣一次

log(n) - binary search

**Space complexity: O(n)**

### 測資

```
let nums = [10,9,2,5,3,7,101,18]; // 4
// nums = [0,1,0,3,2,3]; // 4
// nums = [7,7,7,7,7,7,7]; // 1
// nums = [4,10,4,3,8,9]; // 3
// nums = [6,7,9,4,10,5]; // 4

console.log(lengthOfLIS(nums))
```
