Longest non-decreasing subsequence - Binary search
Intuition\nThe question can be simplified by just solving for "minimum number of elements to change to make the array non decreasing". The reason that is so is 
# Intuition\nThe question can be simplified by just solving for "minimum number of elements to change to make the array non decreasing". The reason that is so is because the question is composed of multiple arrays (k arrays). So if we solve the question for any given array, we can solve it for k arrays.\nLets say K=3 and we have the following array.\n{1 2 3 6 3 2 3 5 10}\nThis gives us 3 arrays that we need to solve for since mod%K can only result in 3 positions {0, 1, 2};\nArray 1 -> 1, 6, 3\nArray 2 -> 2, 3, 5\nArray 3 -> 3, 2, 10\n\nNow the question becomes, how do we solve this question for just one problem.\n\n# Approach\nWe need to redefine the question in reverse. Lets assume the question reads what is the maximum amount of elements that I can leave untouched. If we could find such set of elements, that will give us the answer by inferring that if I don\'t touch X elements, I will have to touch N-X elements. The question becomes what is the Longest Non-decreasing Sequence within an array. The Intuition here is that minimum number of changes is the same thing is as maximum number of non changes.\n\n# Complexity\n- Time complexity:\nO(N) * Log(N);\nAssuming the K = 1 and we have to go through each element trying to find the best position for this current element, we will have to look for in range (0, j -> pos of element) by binary search.\nAssume so far we have found elements for the position 0,1,2,3 as\n[-INF, 3, 5, 6, 9] and we are processing j(4). Since so far we have seen 4 elements and we are the 5th element, we can at most form a length of 5. so we will use l = 0, h = 4, If l gets to 5, this is fine however it can\'t be more than 5. If we find a position where an answer already exists, we will try to improve it for future searches by geting dp[l] = min(dp[l], num)\nNOTE: we can furthe optimize this by making note of furthest length we have found knowing that we can only extend by furthest + 1, we can use furthest as our higher bound.\n\n- Space complexity:\nO(N), we have to maintain a list of elements where j -> last minimum element we have found for length j subsequence where each 0 <= i < j obeys dp[i]<=dp[i+1];\n\n# Code\n```\nconst int INF = 1e9;\nclass Solution {\npublic:\n    int kIncreasing(vector<int>& arr, int k) {\n        int ans = 0;\n        int n = (int)arr.size();\n        for (int i = 0; i<k; ++i) {\n            if (i + k >= (int)arr.size()) continue;\n            //longest increasing subsequence DP initialization (The length will be at most n/k + 2)\n            //length 0 is -INF implying that we can always start from 0 and increase the length to 1\n            vector<int> best(n/k + 2, INF);\n            best[0] = -INF;\n            int count = 0;\n            int bestPos = 0;\n            int idx = i;\n            while (idx < (int)arr.size()) {\n                int curr = arr[idx];\n                int l = 1;\n                int h = bestPos;\n                while (l <= h) {\n                    int m = l + (h-l)/2;\n                    if (best[m] > curr)\n                        h = m-1;\n                    else\n                        l = m+1;\n                }\n                best[l] = min(best[l], curr);\n                bestPos = max(bestPos, l);\n                count++;\n                idx += k;\n            }\n            ans += count - bestPos;\n        }\n        \n        return ans;\n    }\n};\n```
['C++']