LIS in Disguise
We have k independent subarrays in our array, and we need to make those subarrays non-decreasing.\n\nFor each subarray, we need to find the longest non-decreasi
We have `k` independent subarrays in our array, and we need to make those subarrays non-decreasing.\n\nFor each subarray, we need to find the longest non-decreasing subsequence. We keep numbers in that subsequence as-is, and change the rest. We can use the approach from [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/).\n\nBecause `n` is quite large, a quadratic solution would be too slow. So, we should use the O(n log n) solution: monostack with binary search.\n\n**Python 3**\n```python\nclass Solution:       \n    def kIncreasing(self, arr: List[int], k: int) -> int:\n        def LNDS(arr: List[int]) -> int:\n            mono = []\n            for n in arr:\n                if not mono or mono[-1] <= n:\n                    mono.append(n)\n                else:\n                    mono[bisect_right(mono, n)] = n\n            return len(mono)         \n        return len(arr) - sum(LNDS(arr[i::k]) for i in range(k))\n```\n\n**Java**\nWe need to implement `upperBound` by hand, because `binarySearch` in Java is not guaranteed to return the smallest index in case of duplicates.\n\n```java\npublic int kIncreasing(int[] arr, int k) {\n    int longest = 0;\n    for (int i = 0; i < k; ++i) {\n        List<Integer> mono = new ArrayList<>();\n        for (int j = i; j < arr.length; j += k)\n            if (mono.isEmpty() || mono.get(mono.size() - 1) <= arr[j])\n                mono.add(arr[j]);\n            else\n                mono.set(upperBound(mono, arr[j]), arr[j]);\n        longest += mono.size();\n    }\n    return arr.length - longest;\n}\nprivate int upperBound(List<Integer> mono, int val) {\n    int l = 0, r = mono.size() - 1;\n    while (l < r) {\n        int m = (l + r) / 2;\n        if (mono.get(m) <= val)\n            l = m + 1;\n        else\n            r = m;\n    }\n    return l;\n}\n```\n\n**C++**\n```cpp\nint kIncreasing(vector<int>& arr, int k) {\n    int longest = 0;\n    for (int i = 0; i < k; ++i) {\n        vector<int> mono;\n        for (int j = i; j < arr.size(); j += k)\n            if (mono.empty() || mono.back() <= arr[j])\n                mono.push_back(arr[j]);\n            else\n                *upper_bound(begin(mono), end(mono), arr[j]) = arr[j];\n        longest += mono.size();\n    }\n    return arr.size() - longest;\n}\n```
['C', 'Java']