C++ Longest Increasing Subsequence
\nSee my latest update in repo LeetCode\n\n## Solution 1. Longest Increasing Subsequence (LIS)\n\nSplit the numbers in A into k groups: [0, k, 2k, 3k, ...], [1,
\nSee my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Longest Increasing Subsequence (LIS)\n\nSplit the numbers in `A` into `k` groups: `[0, k, 2k, 3k, ...]`, `[1, 1+k, 1+2k, 1+3k, ...]`, ...\n\nCompute the minimum operations needed to make a group non-decreasing. Assume the Longest Increasing Subsequence (LIS) of this group is of length `t`, and the group is of length `len`, then the minimum operations needed is `len - t`.\n\nComputing the length of LIS is a classic problem that can be solved using binary search. See [300. Longest Increasing Subsequence (Medium)](https://leetcode.com/problems/longest-increasing-subsequence/)\n\nThe answer is the sum of minimum operations for all the groups.\n\n```cpp\n// OJ: https://leetcode.com/contest/weekly-contest-272/problems/minimum-operations-to-make-the-array-k-increasing/\n// Author: github.com/lzl124631x\n// Time: O(Nlog(N/k))\n// Space: O(N/k)\nclass Solution {\npublic:\n    int kIncreasing(vector<int>& A, int k) {\n        int N = A.size(), ans = 0;\n        for (int i = 0; i < k; ++i) {\n            vector<int> v{A[i]};\n            int len = 1;\n            for (int j = i + k; j < N; j += k) {\n                auto i = upper_bound(begin(v), end(v), A[j]);\n                if (i == end(v)) v.push_back(A[j]);\n                else *i = A[j];\n                ++len;\n            }\n            ans += len - v.size();\n        }\n        return ans;\n    }\n};\n```
[]