Longest non-decreasing subsequence

Leetcode上有经典题longest increasing subsequence，最优算法是O(n log n)。
但是如果把题稍微改改变成non-decreasing，好像那个最优解就不能直接用了。但是至少还有O(n^2)的DP解。

问题：Given an unsorted array of integers, find the length of longest non-decreasing subsequence.

還是可以做O(n log n), 方法也差不多.

yxchen_ethan 发表于 2019-11-10 19:42
還是可以做O(n log n), 方法也差不多.

那么怎么做呢？

原本問題 Longest increasing subsequence:
# python

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        LIS = [nums[0]]
        
        for num in nums[1:]:
            i = bisect_left(LIS, num)
            if i == len(LIS):
                LIS.append(num)
            elif num < LIS[i]:
                LIS[i] = num
        
        print(LIS)
        return len(LIS)

若是題目改成non-decreasing, 把bisect_left 改成 bisect, 就是non-decreasing的解答了.

bisect和bisect_left, 只差在binary search的時候, comparison是 greater 還是 greater or equal, 回傳的是[lo, up)的上界還是下界(如下).
複雜度同樣是O(log n). 所以longest non-decreasing 一樣O(n log n)可以解掉.

def _bisect(a, x):
    lower_bound, upper_bound = 0, len(a)
    while lower_bound < upper_bound:
        mid = (lower_bound + upper_bound) // 2
        if a[mid] > x:
          upper_bound = mid
        else:
          lower_bound = mid + 1
    return upper_bound

def _bisect_left(a, x):
    lower_bound, upper_bound = 0, len(a)
    while lower_bound < upper_bound:
        mid = (lower_bound + upper_bound) // 2
        if a[mid] >= x:
          upper_bound = mid
        else:
          lower_bound = mid + 1
    return lower_bound