Short and Fast T̶h̶a̶t̶’s̶ w̶h̶a̶t̶ s̶h̶e̶ s̶a̶i̶d̶
Approachfind the longest non monoton increasing subsequence for each sublist, and subtract the length of the subsequences from the total length.Complexity
Time
# Approach
<!-- Describe your approach to solving the problem. -->
find the longest non monoton increasing subsequence for each sublist, and subtract the length of the subsequences from the total length.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n log(n))$$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(n)$$
# Code
```python3 []
class Solution:
    def kIncreasing(self, arr: List[int], k: int) -> int:
        out=n=len(arr)
        for m in range(k):
            a=[]
            for i in arr[m:n:k]:
                if not a or i>=a[-1]:a.append(i)
                else: a[bisect_right(a,i)]=i
            out-=len(a)
        return out
```
['Python3']