Longest Non-Decreasing Subsequence
\nIf you understand the idea of 300. Longest Increasing Subsequence problem, this solution is quite straitforward\n\n Split array to k sub_arrays \n Find minimu
\nIf you understand the idea of [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/) problem, this solution is quite straitforward\n\n* Split array to k sub_arrays \n* Find minimum operation to make each sub_array non-decreasing, and it equal length subarray - longest non-decreasing subsequence of sub_array. Very similar to [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)\n* Time complexity: O(NlogN), space: O(N)\n\n```\nclass Solution:\n    def kIncreasing(self, arr: List[int], k: int) -> int:\n        N, output = len(arr), 0\n        # Create all sub_array\n        sub_arrs = [[] for _ in range(k)]\n        for sub_arr_idx in range(k):\n            for idx in range(sub_arr_idx, N, k):\n                sub_arrs[sub_arr_idx].append(arr[idx])\n\n        # Sum minimum operation of all sub_arrays\n        for sub_arr in sub_arrs:\n            output += len(sub_arr) - self.longest_nondecreasing_subseq(sub_arr)\n        return output\n        \n    def longest_nondecreasing_subseq(self, nums: List[int]) -> int:\n        output = []\n        for num in nums:\n            idx = bisect_right(output, num)\n            if idx == len(output):\n                output.append(num)\n            else:\n                output[idx] = num\n        return len(output)\n```
['Binary Tree']