# [LeetCode 300. Longest Increasing Subsequence ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3808/)
### Daily challenge Jul 9, 2021 (MEDIAN)

>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]`**.

:::info
**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.
:::

:::info
**Example 2:**
**Input:** nums = [0,1,0,3,2,3]
**Output:** 4
:::

:::info
**Example 3:**
**Input:** nums = [7,7,7,7,7,7,7]
**Output:** 1
:::

:::warning
**Constraints:**
* 1 <= nums.length <= 2500
* -104 <= nums[i] <= 104
:::

---

### [Approach 1 : Lower_bound](https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/) :book:
**`8 ms`** **`O(nlogn)`**
:::danger
這個方法只能夠求出正確的長度，**無法保證**得到的 sequence 是正確的。
:::

How is this approach working ?
1. 假設當前數值為 **`最大`** ，可以直接存入 vector 的最後，因為它必然能使 sequence 加長。
2. 若當前數值並 **`非`** 最大，我們可以假設它可能是另外一個更好的開始。

:arrow_down: Here is a simple example for easily understand :arrow_down:

> EXAMPLE : **[1,2,7,8,3,4,5,9,0]**
**1** -> **[1]**
**2** -> **[1,2]**
**7** -> **[1,2,7]**
**8** -> **[1,2,7,8]**
**3** -> **[1,2,3,8]** // we replaced 7 with 3, since for the longest sequence we need only the last number and 1,2,3 is our new shorter sequence
**4** -> **[1,2,3,4]** // we replaced 8 with 4, since the max len is the same but 4 has more chances for longer sequence
**5** -> **[1,2,3,4,5]**
**9** -> **[1,2,3,4,5,9]**
**0** -> **[0,2,3,4,5,9]** // we replaced 1 with 0, so that it can become a new sequence
>
>In the end, we get **[0,2,3,4,5,9]**, which is not the correct sequence ( it should be **[1,2,3,4,5,9]** ), but the length = 6 is the valid answer.

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int > LIS;
        
        for(int i=0; i<nums.size(); i++){
            auto it = lower_bound(LIS.begin(), LIS.end(), nums[i]);
            
            if(it == LIS.end()) LIS.push_back(nums[i]);
            else    *it = nums[i];
        }
        
        return LIS.size();
    }
};

### Approach 2 : Binary Search ( Patience Sorting ) :book:
:::info
implement Greedy Method
* [wiki](https://en.wikipedia.org/wiki/Patience_sorting)
* [slide](https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf) :+1:
:::

**`8 ms`** **`O(nlogn)`**

與 Approach 1 想法相同，但使用 Binary Search 尋找可替換的位置。

> EXAMPLE : **[4,5,6,3]**
> Initial state -> size = 0 ( Always point to next NULL element. If value is biggest, put it in current[size] )
**4** -> size = 0 ---> current = [4]
**5** -> size = 1 ---> current = [4,5]
**6** -> size = 2 ---> current = [4,5,6]
**3** -> size = 3 ---> current = [3,5,6]

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // Binary Search
        int current[nums.size()];
        int size = 0;
        
        for(auto value : nums){
            int left = 0, right = size;
            while(left < right){
                int middle = (left + right) / 2;
                // find current[left] < value <= current[right]
                if(value > current[middle]){
                    left = middle + 1;
                }
                else{
                    right = middle;
                }
            }
            current[left] = value;
            if(left == size)    size++;
        }
        
        return size;
    }
};