###### tags: `Leetcode` `medium` `dynamic programming` `binary search` `python` `c++` `Top 100 Liked Questions`

# 300. Longest Increasing Subsequence

## [題目連結:] https://leetcode.com/problems/longest-increasing-subsequence/

## 題目:
Given an integer array nums, return the length of the longest strictly increasing **subsequence**.
* A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

**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:使用DP
* 定義dp[i]表示**從頭到num[i]最長subsequence**
* 雙迴圈遍歷
* 第一圈:for **i** in range(len(nums))
* 第二圈 for **j** in range(i)
* 若nums[j]<nums[i]，則可以判斷
* dp[i]=max(dp[i],dp[j]+1)
* 原本的or繼承後+1
* 由於第二迴圈，每次皆從頭判斷，因此time: O(n^2)

## Python_Sol1: DP

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #time:O(n^2)
        dp=[1]*len(nums)
        #dp[i]表示從頭到num[i]最長subsequence
        res=float('-inf')
        for i in range(len(nums)):
            for j in range(i):
                if nums[j]<nums[i]:
                    dp[i]=max(dp[i],dp[j]+1)
            res=max(res,dp[i])
        return res

result=Solution()
ans=result.lengthOfLIS(nums = [10,9,2,5,3,7,101,18])
print(ans)

* 法2: 使用Binary Search概念
* time: **O(NlogN)**
* Step1:
* 將nums[0]先加入到res
* Step2:
* 依序遍歷數組後面的數:
* **Case1**:若當前數字比res[-1]更大，則將此數字加到res
* **Case2**:若當前數字比res[0]更小，則取代res[0]
* **Case3**:若當前數字大小在res中間，則選mid的位置，當前數字取代nums[mid]
* mid:即為res中第一個比當前數字大的位置
* 最後答案即為len(res)
* **然而res中的數字組合不一定是合法的!!**

* trace:

nums = [10,9,2,5,3,7,101,18]
res=[10]

for i in range(1,len(nums)):
* loop1: 9
case2: 9<res[0]
-> res=[9]

* loop2: 2
case2: 2<res[0]
-> res=[2]

* loop3: 5
case1: 5>res[-1]
-> res=[2,5]

* loop4: 3
case3: -> res=[2,3]

* loop5: 7
case1: -> res=[2,3,7]

* loop6: 101
case1: -> res=[2,3,7,101]

* loop7: 18
case3: -> res=[2,3,18,101]

注意!! 此時res中順序: 並不是合法解!! 
但res的長度始終保持著當前最長序列的長度~~

final ans: len(res)=4 

## Python_Sol2:

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #time: O(nlogn)
        if len(nums)==0:
            return 0
        res=[nums[0]]
        for i in range(1,len(nums)):
            #若新的值 比res最後一個大 則直接加入
            if nums[i]>res[-1]:
                res.append(nums[i])
            #若小於res[0] 則取代res[0]
            elif nums[i]<res[0]:
                res[0]=nums[i]
            else: #若在中間 選mid的位置 nums[i]取代nums[mid]
                mid = self.findMid(res,nums[i])
                res[mid]=nums[i]
        return len(res)
    
    def findMid(self,res,num):
        head=0
        tail=len(res)-1
        while head<=tail:
            mid=(head+tail)//2
            if res[mid]==num:
                return mid
            elif res[mid]>num:
                tail=mid-1
            else:
                head=mid+1
        return head

result=Solution()
ans=result.lengthOfLIS(nums = [10,9,2,5,3,7,101,18])
print(ans)

## C++:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size()==0)
            return 0;
        vector<int> res;
        res.push_back(nums[0]);
        for (int i=1; i<nums.size(); i++){
            if (nums[i]>res.back())
                res.push_back(nums[i]);
            else if (nums[i]<res[0])
                res[0]=nums[i];
            else{
                int mid=find(res,nums[i]);
                res[mid]=nums[i];
            }
        }
        return res.size();
    }

    int find(vector<int>& res, int val){
        int head=0, tail=res.size()-1;
        while (head<=tail){
            int mid=(head+tail)/2;
            if (res[mid]==val)
                return mid;
            else if (res[mid]<val)
                head=mid+1;
            else
                tail=mid-1;
        }
        return head;
    }
};