Python [Longest non-decreasing subsequence]
Suppose that you have a function lnds(sub) that gives you the longest non-decreasing subsequence of a subarray. For example, sub = [1, 2, 3, 3, 2, 2, 2] would r
Suppose that you have a function `lnds(sub)` that gives you the longest non-decreasing subsequence of a subarray. For example, `sub = [1, 2, 3, 3, 2, 2, 2]` would return `5` which corresponds to the subsequence `[1, 2, 2, 2, 2]`.\n\nThe longest strictly increasing subsequence is actually Problem 300. Compared to that all we need to do is `bisect_right` instead of `bisect_left` to take ties into account. (In the example above, using `bisect_left` would result in `3`, which corresponds to `[1, 2, 3]`.)\n\nIn this question, `k` divides the given array into at most `k` disjoint subarrays. For each subarray, the minimum number of operations is `len(sub) - lnds(sub)`.\n\nTime: `O(N)`\nSpace: `O(N)`\n\n```python\nclass Solution:\n    def kIncreasing(self, A, k):\n        def lnds(sub):\n            L = 0\n            DP = []\n            for x in sub:\n                #Leetcode 300 - use bisect_left instead\n                i = bisect.bisect_right(DP, x)\n                if i == len(DP):\n                    DP.append(x)\n                else:\n                    DP[i] = x\n                if i == L:\n                    L += 1\n            return L\n        \n        ans = 0\n        for i in range(k):\n            sub = A[i:len(A):k]\n            ans += len(sub) - lnds(sub)\n        return ans\n```
[]