✅ [Python/C++/Java] LIS || 100% Faster || Detailed Explanation || Clean and Easy to Understand
First divide arr into k groups and consider each group individually.\n In each group, we need to find out the length of the longest increasing sequence, because
* First divide arr into k groups and consider each group individually.\n* In each group, we need to find out the length of the longest increasing sequence, because the longest increasing sequence does not need to be operated, and the remaining positions can be set to the value of the previous or next in the longest increasing sequence.\n* For example, `arr = [2, 3, 4, 2, 3 , 3]`\n\t* the longest increasing sequence is [2, 2, 3, 3], that is [**2**, 3, 4, **2**, **3** , **3**]\n\t* we can modify arr[1] from 3 to 2 and arr[2] from 4 to 2, and then the arr is increasing, that is [2, 2, 2, 2, 3, 3]\n\t* after all we need to make 2 operations to make `arr = [2, 3, 4, 2, 3 , 3]` increasing, that is `len(arr) - len(lis(arr))`\n\n[Prob 300 Longest-Increasing-Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation), **@dietpepsi explained very well, I just copied his explanation below.**\n\n`tails` **is an array storing the smallest tail of all increasing subsequences with length** `i+1` in `tails[i]`.\nFor example, say we have `nums = [4,5,6,3]`, then all the available increasing subsequences are:\n\n```\nlen = 1   :      [4], [5], [6], [3]   => tails[0] = 3\nlen = 2   :      [4, 5], [5, 6]       => tails[1] = 5\nlen = 3   :      [4, 5, 6]            => tails[2] = 6\n```\nWe can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.\n\n\n\n```\n(1) if x is larger than all tails, append it, increase the size by 1\n(2) if tails[i-1] < x <= tails[i], update tails[i]\n```\n\n\n**If you have any question, feel free to ask. If you like the solution or the explanation, Please UPVOTE!**\n\n**Python 100% Faster**\n```\nclass Solution(object):\n    def kIncreasing(self, arr, k):\n        ans = len(arr)\n        for i in range(k):\n            tails = []\n            for j in range(i, len(arr), k):\n                if tails and tails[-1] > arr[j]:\n                    tails[bisect.bisect(tails, arr[j])] = arr[j]\n                else:\n                    tails.append(arr[j])\n            ans -= len(tails)\n        return ans\n```\n\n**C++ 63.64% Faster**\n```\nclass Solution {\npublic:\n    int kIncreasing(vector<int>& arr, int k) {\n        int ans = arr.size();\n        for(int i = 0; i < k; i ++) {\n            vector<int> tails;\n            for(int j = i; j < arr.size(); j += k) {\n                if(tails.size() == 0 or arr[j] >= tails[tails.size() - 1]) {\n                    tails.push_back(arr[j]);\n                } else {\n                    tails[upper_bound(tails.begin(), tails.end(), arr[j]) - tails.begin()] = arr[j];\n                }\n            }\n            ans -= tails.size();\n        }\n        return ans;\n    }\n};\n```\n**Java 100% Faster**\n* I\'m not very good at Java, and I did not find a function like bisect in Python, so I implement one below, that\'s why the java code is longer than C++ or Python above.\n* I hope friends who are good at java can help me simplify the Java code below.\n```\nclass Solution {\n    public int kIncreasing(int[] arr, int k) {\n        int ans = arr.length;\n        int[] tails = new int[arr.length];\n        for (int i = 0; i < k; i ++) {\n            int size = 0;\n            for (int j = i; j < arr.length; j += k) {\n                if (size == 0 || arr[j] >= tails[size - 1]) {\n                    tails[size ++] = arr[j];\n                } else {\n                    int low = 0, high = size - 1;\n                    while (low <= high) {\n                        int mid = (low + high) / 2;\n                        if (tails[mid] <= arr[j] && tails[mid + 1] > arr[j]) {\n                            tails[mid + 1] = arr[j];\n                            break;\n                        } else if (tails[mid + 1] <= arr[j]) {\n                            low = mid + 1;\n                        } else {\n                            high = mid - 1;\n                        }\n                    }\n                    if (low > high) {\n                        tails[0] = arr[j];\n                    }\n                }\n            }\n            ans -= size;\n        }\n        return ans;\n    }\n}\n```\n\n**If you have any question, feel free to ask. If you like the solution or the explanation, Please UPVOTE!**
['C', 'Python', 'C++', 'Java']