# Leetcode 解題速記 300. Longest Increasing Subsequence
###### tags: `LeetCode` `C++`
題敘:
---
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].

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

測資範圍:
---
* `1 <= nums.length <= 2500`
* `-104 <= nums[i] <= 104`

解題筆記:
---
這題一開始看到時直覺想到就是使用DP解題，在看過網路上其他高手的解法後才發現可以使用binary search進一步優化時間複雜度。

我們的思路是，遍歷過整個nums中的數字，`dp[i]`所記錄的是在i+1長度下，最優的子序列尾數。當我們遇到長度相同的子序列時，例如[1,2,8]與[3,4,5]，要怎麼判斷哪個比較符合題目的要求呢?

此時，我們只需要考慮子序列中最後一個數字的大小即可，因為越小的尾數，在之後的過程中找到比它更大的數進而擴展的機率更高。上述的例子中，[3,4,5]就會是比較好的子序列。

同理，當我們遇到尾數相同的子序列時，例如[1,2,5]與[3,4,5]，在它們長度都為3的情況下，兩個子序列是等價的。但是，當我們將長度降到2，亦即[1,2]與[3,4]，此時前者就會優於後者，因為2小於4。

這題的解法就是建立在這個思路基礎上，我們在遍歷nums中所有數字的時候，如果這個數字n比目前dp所記錄的子序列中所有數字都還要大，那我們就擴展目前的子序列，讓這個新數字n成為新的尾數。如果這個數字n的大小恰好在子序列中間的某個位置，我們就使用STL的`lower_bound()`，也就是二分搜，來找到這個位置，然後把其上的數字替換成n。

假設當前dp紀錄的LTS是[1,2]而n=8，因為8>2，所以我們選擇擴增子序列為[1,2,8]。此時這個子序列可以這樣解讀 :

[1,2,8] => [1], [*,2], [*,*,8] #長度為i的LTS當下最優的尾數
LTS長度 :  i=1   i=2     i=3

假設下一個數字n為5，因為5<8，所以我們將i=3時最優的數字從8換成5，新的子序列就是[1,2,5]

以此類推繼續往下遍歷，最後取得的`dp.size()`就是我們在所有數字nums中可以找到最好的LTS。

程式碼:
---
`Time Complexity : O(nlogn)`

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        for (int n : nums)
        {
            auto it = lower_bound(dp.begin(), dp.end(), n);
            if (it == dp.end())
            {
                dp.push_back(n);
            }
            else
            {
                *it = n;
            }
        }
        return dp.size();
    }
};