Golang 100/80
Logic in comments. O(n * log n/k)time; O(n/k) space\n\nfunc kIncreasing(arr []int, k int) int {\n\n    // the name of this problem is not optimal. We\'re not ac
Logic in comments. `O(n * log n/k)`time; `O(n/k)` space\n```\nfunc kIncreasing(arr []int, k int) int {\n\n    // the name of this problem is not optimal. We\'re not actually trying to make the suqsequences increasing\n    // we\'re trying to make them non-decreasing\n\n    // the general approach is the same idea as https://leetcode.com/problems/longest-increasing-subsequence/\n    // with 2 changes    \n    // 1) that problem is looking for truly increasing subsequences. the change necessary to move from\n    // increasing to non-decreasing is to use strict comparison (>) instead of parial comparison (>=)\n    // 2) that problem deals with the full array. this problem asks us to split the full array into k subarrays\n    // those subarrays do not intefere with each other in any way. each of those sub-arrays has len n/k or n/k-1\n\n    // after accounting for strict vs partial, the only question is whether to work the array from left to right\n    // or work with each of the k subarrays. working from left to right requires more memory because we have to\n    // maintain a memo for each of the k subarrays as we go. in the worst case, we have to use O(n) memory for that\n    // working each subproblem 1 at a time means we only need O(n/k) extra space, since that the is maximum size\n    // of the memo for each subarray\n\n    // create a variable to store the answer\n    var ans int\n\n    // start at each pos < k\n    for l := 0; l < k; l++ {\n\n        // construct a memo to hold the lowest end value for non-dec subseq of each length up to this point\n        // at each step len(tails) is the longest subsequence we\'ve built and tails[i] is the lowest value\n        // we can have at the end of a subseq of len(i)\n        tails := []int{}\n\n        // iterate over values of sub-array starting at l\n        var r int\n        for r = 0; l+k*r < len(arr); r++ {\n            // get the value of the sub-array\n            x := arr[l+k*r]\n\n            // binary search for the len of the longest subseq we can update\n            m := sort.Search(len(tails), func(m int) bool {\n                // use partial ordering to account for non-decreasing instead of increasing\n                return tails[m] > x\n            })\n\n            if m == len(tails) {\n                // if we can add x to the longest subseq, add that to the memo\n                tails = append(tails, x)\n            } else {\n                // otherwise, update the exsisting subseq\'s tail\n                tails[m] = x\n            }\n\n        }\n\n        // the number of values we need to change in this sub array is equal to len(subarray) - len(longest subseq)\n        // r = len(subarray); len(longest subseq) = len(tails)\n        ans += r - len(tails)\n    }\n    \n    return ans\n}\n\n```
['Binary Search', 'Dynamic Programming']