300. 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].

解法一：DP #

建立一個dp array，dp[i]代表的是以nums[i]做為結尾的seq的最大長度，做法是搜尋 dp[0] ~ dp[i-1]，找到最大的sub-LIS，將其+1更新dp[i]。

c++

int lengthOfLIS(int* nums, int numsSize){
    int dp[numsSize];
    int max = 1;
    for(int i = 0; i < numsSize; i++) {
        dp[i] = 1;
        for(int j = 0; j < i; j++)
            dp[i] = (nums[i]>nums[j] && dp[i] <= dp[j]) ? dp[j]+1: dp[i];
        max = dp[i]>max ? dp[i] : max;
    }
    return max;
}

func lengthOfLIS(nums []int) int {
    dp := make([]int, len(nums))
    for i := 0; i < len(dp); i++ {
        dp[i] = 1
    }
    for i := 1; i < len(dp); i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] && dp[j] >= dp[i] {
                dp[i] = dp[j]+1
            }
        }
    }
    return max(dp)
}

func max(lst []int) int {
    max := 1
    for _, v := range lst {
        if v > max {
            max = v
        }
    }
    return max
}

TC: n^2

解法二：DP+Binary Search #

建立一個dp array，dp[i]代表的是長度i的最佳結尾，關於最佳結尾，可以思考 1,2,3 和 1,2,5誰對於這個題目來說更有未來，肯定是前者吧因為之後出現4後者的長度不會再增加了，前者卻可以變成1,2,3,4。每個新插入的數只有兩種可能

如果比目前dp[-1]（最後一個）大，可以直接串上, e.g., 1,2,3–插入4–>1,2,3,4
如果比dp[-1]小，就用bs更新dp， e.g., 1,2,5–插入4–>1,2,4

搜尋的部分參考這題。最後回傳dp長度即可。

c++

int lengthOfLIS(vector<int>& nums) {
    vector<int> vect;
    for(auto &num: nums) {
        if(!vect.size() || vect.back() < num)
            vect.push_back(num);
        else {
            auto idx = lower_bound(vect.begin(), vect.end(), num);
            *idx = num;
        }
    }
    return vect.size();
}

int lengthOfLIS(int* nums, int numsSize){
    int dp[numsSize];
    int idx = 0;
    for(int i = 0; i < numsSize; i++) {
        if(!idx || (dp[idx-1] < nums[i])) {
            dp[idx] = nums[i];
            idx++;
        } else {
            int l = 0, r = idx-1; 
            while(l <= r) {
                int mid = (l+r) >> 1;
                if(dp[mid] >= nums[i])
                    r = mid-1;
                else
                    l = mid+1;
            }
            dp[l] = nums[i];
        }
    }
    return idx;
}

func lengthOfLIS(nums []int) int {
    dp := []int{}
    for _, n := range nums {
        if len(dp) == 0 || n > dp[len(dp)-1] {
            dp = append(dp, n)
        } else {
            l, r := 0, len(dp)-1
            for l <= r {
                mid := (l+r)>>1
                if dp[mid] >= n {
                    r = mid - 1
                } else if dp[mid] < n {
                    l = mid + 1
                }
            }
            dp[l] = n
        }
    }
    return len(dp)
}

python

def lengthOfLIS(self, nums: List[int]) -> int:
    dp = []
    for num in nums:
        if not dp or dp[-1] < num:
            dp.append(num)
        else:
            idx = bisect.bisect_left(dp, num)
            dp[idx] = num
    return len(dp)