C++ | With explanation | longest non-decreasing subsequence
Explanation:-\n1. if we see carefully then we will find that we have to make these subsequences non-decreasing:-\n  arr[i]<=arr[i+k]<=arr[i+2k]... so on\n    he
**Explanation:-**\n1. if we see carefully then we will find that we have to make these subsequences non-decreasing:-\n  ```arr[i]<=arr[i+k]<=arr[i+2k]... so on```\n    here ```i``` wil start from ```0``` and go upto ```k-1```\n2. For making these non-decreasing we have to find ```longest non-decreasing subsequence``` in these sequences\t.\n3. Our answer will be length(temp)-length(longest non-decreasing subsequence) in ```temp sequence```\n\t\n```\n\tclass Solution {\npublic:\n    int kIncreasing(vector<int>& arr, int k) {\n        int size=arr.size(),ans=0;\n            for(int i=0;i<k;i++){\n                vector<int>temp;\n                // finding subsequence which follows arr[i]<=arr[i+k]<=arr[i+2k]. this pattern\n                for(int j=i;j<size;j+=k)\n                    temp.push_back(arr[j]);\n                // getting the length of longest non-decreasing subsequence in this pattern\n                int cnt=helper(temp);\n                // elements which are not a part of this longest non-decreasing subsequence are our answer(we have to change them)\n                ans+=temp.size()-cnt;\n                \n            }\n        return ans;\n    }\n    // finding longest non-decreasing subsequence\n    int helper(vector<int>&nums){\n          vector<int> lis;\n        for (int i = 0; i < nums.size(); ++i) {\n            int x = nums[i];\n            if (lis.empty() || lis[lis.size() - 1] <= x) { \n                lis.push_back(x);\n                nums[i] = lis.size();\n            } else {\n                int idx = upper_bound(lis.begin(), lis.end(), x) - lis.begin(); \n                lis[idx] = x; \n                nums[i] = idx + 1;\n            }\n        }\n        // cout<<lis.size()<<endl;\n        return lis.size();\n    }\n};\n```\n\t\nDo **UPVOTE** if it helps :)
['C']