Java | O(NlogN) | Binaray-Search for LIS| Detailed Explanation
The problem is asking us to find a longest non-decreasing subsequence\n1. case when k == 1:\nwe are trying to minimize the change operation -> if we find a long
The problem is asking us to find a longest non-decreasing subsequence\n**1. case when k == 1:**\nwe are trying to minimize the change operation -> if we find a longest non-decreasing subsequence for arr, then \nthe result would be **arr.length - length of LIS**\n\n**2. how to find a LIS ?**\nwe use an ArrayList to record the longest non-decreasing subsequence, if the list is empty or the incoming element A >= the last element in list, we add incoming element to list, otherwise we find a best position i using binary-search, so that **list[i - 1] <= A < list[i]**, and set list[i] to A.\ne.g arr = [4, 8, 9, 6, 6, 2], k = 1\n1st iteration: list is empty, add 4, list becomes [4]\n2nd: 8 > 4, add 8, list becomes [4, 8]\n3rd: 9 > 8, add 9, list becomes [4, 8, 9]\n4th: 6 < 9, binary search the index, we find position = 1, set list[1] to 6, list becomes [4, 6, 9]\n5th: 6 < 9, posiiton = 2, set list[2] to 6, list becomes [4, 6, 6]\n6th: list becomes [2, 6, 6]\nThe minimum operation would be **length of list - list.size()**\n\n**3. case when k > 1**\nsam as case 1, only we are finding k LIS rather than 1 LIS, for each subarray with k intervals, we calculate **length of subarray - LIS.size()** and add it to result. \n\n```\nclass Solution {\n    public int kIncreasing(int[] arr, int k) {\n        //arr = new int[]{12,6,12,6,14,2,13,17,3,8,11,7,4,11,18,8,8,3};\n        //k = 1;\n        int res = 0;\n        for (int i = 0; i < k; i++) {\n            int j = i;\n            ArrayList<Integer> list = new ArrayList();\n            int count = 0;\n            while (j < arr.length) {\n                if (list.isEmpty() || list.get(list.size() - 1) <= arr[j]) {\n                    list.add(arr[j]);\n                } else {\n                    list.set(bs(list, arr[j]), arr[j]);\n                }\n                j += k;\n                count++;\n            }\n            res += count - list.size();\n        }\n        return res;\n    }\n\n    public int bs(ArrayList<Integer> list, int num) {\n        int l = 0;\n        int r = list.size() - 1;\n        while (l <= r) {\n            int mid = (l + r) >> 1;\n            if (list.get(mid) <= num) {\n                l = mid + 1;\n            } else {\n                r = mid - 1;\n            }\n        }\n        return l;\n    }\n}\n```
['Binary Tree']