Beats 100% LIS Solution Explained Python
\n\nHow to find the min no. of operations needed to make a sequence not decreasing?\n\nYou find the longest increasing subsequence (LIS) of the sequence.\nAll t
![image.png](https://assets.leetcode.com/users/images/8c898028-0426-42d0-8c2b-c3709f2bc72e_1673460615.1070132.png)\n\n**How to find the min no. of operations needed to make a sequence not decreasing?**\n\nYou find the longest increasing subsequence (LIS) of the sequence.\nAll the elements not in LIS needed to modified.\n\nIn this problem there are k sequences, each beginning from index `0,...,k-1`\n\n**Time: O(k log(n/k))\nSpace: O(n/k)**\n```\ndef kIncreasing(self, arr: List[int], k: int) -> int:\n    n = len(arr)\n\n    def LIS(start):\n        lis = []\n        for i in range(start, n, k):\n            if not lis or arr[i] >= lis[-1]:\n                lis.append(arr[i])\n            else:\n                lis[bisect_right(lis, arr[i])] = arr[i]\n        return ceil((n - start)/k) - len(lis)\n    \n    return sum([LIS(start) for start in range(k)])\n```
['Dynamic Programming', 'Python']