Easy solution using longest non-decreasing subsequence
Intuition\nThe intutition is simple to take all subarrays of the defined types. ie. subarrays (0,k,2k ...), (1,k+1,2k+1...) and so on.\nFor all this subarrays w
# Intuition\nThe intutition is simple to take all subarrays of the defined types. ie. subarrays (0,k,2*k ...), (1,k+1,2*k+1...) and so on.\nFor all this subarrays we will find how many elements we need to update so that the subarrays become non-decreasing.\n\n# Approach\nAll the subarrays that are formed are independant of each other. So we will find answers individually for all of these subarrays.\nLets try to find the answer for these individual subarrays.\nFor this we can find the longest non-decreasing subsequence and we will increase the remaining elements for the which are not part of the subsequence.\nSo the answer will be (sizeof(subarray) - lnds);\n\n# Complexity\n- Time complexity:\n- O(nlog(n));\n\n- Space complexity:\n- O(nlog(n))\n\n# Code\n```\nclass Solution {\npublic:\n\n    int lengthOfLNDS(vector<int>& nums) {\n    if (nums.empty()) return 0;\n\n    vector<int> dp;\n\n    for (int num : nums) {\n        auto it = std::upper_bound(dp.begin(), dp.end(), num);\n\n        if (it == dp.end()) {\n            dp.push_back(num);\n        } else {\n            *it = num;\n        }\n    }\n\n    return dp.size();\n}\n\n\nint kIncreasing(vector<int>& a, int k) {\n\n    int n = a.size();\n    int ans = 0;\n    for (int i = 0; i < k; i++) {\n        vector<int>l;\n        for (int j = i; j < n; j += k) {\n            l.push_back(a[j]);\n        }\n        int r = lengthOfLNDS(l);\n        ans += (l.size() - r);\n    }\n    return ans;\n}\n};\n```
['C++']