题解 | #最长递增子序列#

python3 和C++实现均仅通过部分样例

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        if (arr.size() < 2)  return arr;
        vector<int> dp;
        dp.push_back(arr[0]);
        for (int i = 1; i < arr.size(); ++i){
            if (arr[i] > dp.back()) {
                dp.push_back(arr[i]);
            } else {
                auto itr = lower_bound(dp.begin(), dp.end(), arr[i]);
                *itr = arr[i];
            }
        }
        return dp;
    }
};

class Solution:
    def bisect_left(self, dp, target):
        lo = 0
        hi = len(dp)
        while lo < hi:
            mid = (lo + hi) // 2
            if dp[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def LIS(self , arr ):
        # write code here
        length = len(arr)
        if len(arr) < 1:
            return []
        dp = [arr[0]]
        for i in range(1, length):
            if arr[i] > dp[-1]:
                dp.append(arr[i])
            else:
                index = self.bisect_left(dp, arr[i])
                dp[index] = arr[i]
        return dp