C++ LIS variant
\n\n\n\n// Ideas / Approach: an variant of LISS ie the Longest Increasing SubSeq ~~\n// because this problem is about increasing sequence. BTW, if it\'s about d
\n\n\n```\n// Ideas / Approach: an variant of LISS ie the Longest Increasing SubSeq ~~\n// because this problem is about increasing sequence. BTW, if it\'s about decreasing sequence, the\n// LISS can apply as well.\n// * If k == 1, then the answer is A.size() - LIS(A), where A is the input array.\n// * If k > 1, then the array a has k independent subsequences, and each of the subsequences can be\n// handled as if it\'s a separate array for k==1.\n// * Time Complexity: O(n log n)\nclass Solution {\npublic:\n    int kIncreasing(vector<int>& A, int k) {\n        int ops = 0;\n        vector<int> mono; // mono stack/vec for LISS\n        for (int j = 0; j < k; ++j) { // j is the offset for the sub-series\n            int subLen = 0;\n            for (int i = j; i < A.size(); i += k) {\n                ++subLen;\n                const auto e = A[i];\n                if (mono.empty() || mono.back() <= e) {\n                    mono.push_back(e); // grow the mono stack/vector for LISS.\n                } else { // here the mono.back() must > e, so iter is always valid.\n                    auto iter = upper_bound(mono.begin(), mono.end(), e);\n                    // improve the health/potential of the element, so that the LISS mono vec is\n                    // better poised for future growth.\n                    *iter = e;\n                }\n            }\n            ops += (subLen - mono.size()); // need these # of ops to fix this sub-series.\n            mono.clear();\n        }\n\n        return ops;\n    }\n};\n```\n
['C']