題目描述

給你一個(gè)整數(shù)數(shù)組 nums ，找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度。
子序列 是由數(shù)組派生而來(lái)的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。

示例 1：
輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長(zhǎng)遞增子序列是 [2,3,7,101]，因此長(zhǎng)度為 4 。

示例 2：
輸入：nums = [0,1,0,3,2,3]
輸出：4

示例 3：
輸入：nums = [7,7,7,7,7,7,7]
輸出：1

題解

思路1:動(dòng)態(tài)規(guī)劃

定義dp[i]為以i元素結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度

我們從小到大計(jì)算dp數(shù)組的值，在計(jì)算dp[i]之前，我們已經(jīng)計(jì)算出dp[0…i?1] 的值，則狀態(tài)轉(zhuǎn)移方程為
dp[i] = max(dp[j]) + 1 (0<=j<i 且 num[i]>nums[j])
邊界條件：dp[0] = 1

// OC
+ (int)lengthOfLIS1:(NSArray *)nums {
    int n = (int)nums.count;
    int dp[n];
    dp[0] = 1;
    int res = 1;
    for (int i=1; i<n; i++) {
        int tempLen = 1;
        for (int j=0; j<i; j++) {
            if ([nums[i] intValue] > [nums[j] intValue]) {
                tempLen = MAX(tempLen, dp[j]+1);
            }
        }
        dp[i] = tempLen;
        if (dp[i] > res) {
            res = dp[i];
        }
    }
    return res;
    
}

// Swift
    static public func lengthOfLIS1(_ nums:[Int]) -> Int {
        let n = nums.count
        var dp = Array(repeating: 1, count: n)
        var res = 1
        for i in 1..<n {
            for j in 0..<i {
                if nums[i] > nums[j] {
                    dp[i] = max(dp[i], dp[j] + 1)
                }
            }
            if res < dp[i] {
                res = dp[i]
            }
        }
        return res
        
    }

思路2:貪心算法+二分法查找

想獲得最長(zhǎng)遞增子序列，我們需要讓遞增子序列上升得盡可能的慢，也就是說(shuō)每次在遞增子序列最后加上的那個(gè)數(shù)盡可能的小

定義dp[len]為長(zhǎng)度為len的遞增子序列末尾最小元素，邊界條件：dp[1] = nums[0]

d[len]是關(guān)于len單調(diào)遞增的

對(duì)于任意長(zhǎng)度為i的遞增子序列(末尾元素為x)，我們?cè)谀┪矂h除一個(gè)元素，都可以得到一個(gè)長(zhǎng)度為i-1的遞增子序列(末尾元素為y),很明顯y<x。
dp[i] 表示長(zhǎng)度為i的遞增子序列的最小元素，即dp[i] = min(x0,x1,x2...),dp[i-1] 表示長(zhǎng)度為i-1的遞增子序列的最小元素，即dp[j] = min(y0,y1,y2...),又由于x0>y0,x1>y1,...,則dp[i]>dp[i-1]
因而d[len]是關(guān)于len單調(diào)遞增的。

我們從小遍歷數(shù)組nums，比較nums[i]和dp[len],更新len和dp[len]
如果nums[i] > dp[len],表示當(dāng)前長(zhǎng)度len的遞增子序列的末尾元素小于nums[i],則len=len+1,dp[len] = nums[i];
如果nums[i] < dp[len],則在dp數(shù)組中查找，找到一個(gè)k(0<k<=len)，dp[k-1]<nums[i]<dp[k],更新dp[k] = nums[i],如果找不到k，則說(shuō)明所有dpj都比nums[i],則更新dp[0] = nums[i]

在nums[i] < dp[len]，查找k的過(guò)程中，由于dp是單調(diào)遞增的，我們可以通過(guò)二分法查找，即查找第一個(gè)比nums[i]小的數(shù)d[k],更新d[k+1]=nums[i]

// OC
+ (int)lengthOfLIS2:(NSArray *)nums {
    int n = (int)nums.count;
    if (n<=1) {
        return n;
    }
    // dp[len]為長(zhǎng)度為len的遞增子序列末尾最小元素，邊界條件：dp[1] = nums[0]
    int dp[n];
    dp[1] = [nums[0] intValue];
    int len = 1;
    for (int i=1; i<n; i++) {
        if ([nums[i] intValue] > dp[len]) {
            len ++;
            dp[len] = [nums[i] intValue];
        }else{
            int left = 1;
            int right = len;
            int pos = 0;
            // 二分法查找第一個(gè)小于nums[i]的k
            while (left <= right) {
                int mid = (left+right)/2;
                if ([nums[mid] intValue] < [nums[i] intValue]) {
                    pos = mid;
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }
            
            dp[pos+1] = [nums[i] intValue];
        }
    }
    return len;
}

// Swift
    static public func lengthOfLIS2(_ nums:[Int]) -> Int {
        
        if nums.count <= 1 {return nums.count}
        
        let n = nums.count
        var dp = Array(repeating: -1, count: n+1)
        
        var len = 1
        dp[1] = nums[0]
        
        for i in 1..<n {
            if nums[i] > dp[len] {
                len += 1
                dp[len] = nums[i]
            }else{
                var l=1
                var r=len
                var pos = 0
                while l<=r {
                    let mid = (l+r)/2
                    if dp[mid] < nums[i] {
                        pos = mid
                        l = mid+1
                    }else{
                        r = mid-1
                    }
                }
                dp[pos+1] = nums[i]
            }
        }

        return len
        
    }

參考：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xwhvq3/
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/