C++ 243ms beats 99% run LIS k times
Separate arr into k subsequences. \nNumber of operations on each subsequence would be total elements count minus LIS length. \nFor example, 1 subsequence might 
Separate arr into k subsequences. \nNumber of operations on each subsequence would be total elements count minus LIS length. \nFor example, 1 subsequence might be [1,4,3] generated from arr=[1,2,4,5,3] when k=2. Then, total elements count is 3 and LIS length would be 2, ie. [1,3]. Thus the operations count would be 3-2=1 for this subsequence.\nObviously, total operations is the sum of number of operations on every subsequences.\n\nSo, here we go. \n\n```\nclass Solution {\npublic:\n    int kIncreasing(vector<int>& arr, int k) {\n        int N = arr.size();\n        int ans = 0;\n        vector<int> dp;\n\n        for (int i = 0; i < k; ++i) {\n            // run LIS for every i between [0, k-1], storing LIS result in dp\n            dp.clear();\n            int j = i;\n            while (j < N) {\n                auto it = upper_bound(dp.begin(), dp.end(), arr[j]);\n                if (it == dp.end()) {\n                    dp.push_back(arr[j]);\n                } else {\n                    *it = arr[j];\n                }\n\n                j += k;\n            }\n            ans += (j-i)/k - dp.size();\n        }\n\n        return ans;\n    }\n};\n```\n\nTime Complexcity = k * time complexity of LIS for n/k elements = O(k * (n/k)*log(n/k)) = O(n*log(n/k))\n\nIf there exists any error in my post, please point it out. I appreciate it. Thanks.
['C']