[Python] Short LIS, explained
There are two observations we need to make.\n1. It is independent to consider subproblems on 0, k, 2k, ..., 1, k+1, 2k+1, ... and so on.\n2. For each subproblem
There are two observations we need to make.\n1. It is independent to consider subproblems on `0, k, 2k, ...`, `1, k+1, 2k+1, ...` and so on.\n2. For each subproblem it is enough to solve LIS (longest increasing(not strictly) subsequence) problem. Indeed, if we have LIS of length `t`, than we need to change not more than `R-t` elements, where `R` is size of our subproblem. From the other side, we can not change less number of elements, because if we changed `< R- t` elements it means that `> t` elements were unchanged and it means we found LIS of length `> t`. This is called **estimate + example** technique in math.\n\n\n#### Complexity\nIt is `O(n log n)` for time and `O(n)` for space.\n\n#### Code\n```python\nfrom bisect import bisect\n\nclass Solution:\n    def LIS(self, nums):\n        dp = [10**10] * (len(nums) + 1)\n        for elem in nums: dp[bisect(dp, elem)] = elem  \n        return dp.index(10**10)\n    \n    def kIncreasing(self, arr, k):\n        ans = 0\n        for i in range(k):\n            A = arr[i::k]\n            ans += len(A) - self.LIS(A)\n    \n        return ans\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
[]