Swift LIS (but actually Longest Non-Decreasing Sequence)
Inspired from @hiepit\nhttps://leetcode.com/problems/minimum-operations-to-make-the-array-k-increasing/discuss/1635013/C%2B%2BPython-Longest-Non-Decreasing-Subs
Inspired from @hiepit\nhttps://leetcode.com/problems/minimum-operations-to-make-the-array-k-increasing/discuss/1635013/C%2B%2BPython-Longest-Non-Decreasing-Subsequence-Clean-and-Concise\nThe description from above article is very nice details.\n\n```\nclass Solution {\n    // Time: O(nlogn)\n    // Space: O(1)\n    func lengthOfLNDS(_ nums: [Int]) -> Int {\n        var sub: [Int] = [nums[0]]\n        for i in 1..<nums.count {\n            let num = nums[i]\n            if num >= sub.last! {\n                sub.append(num)\n            } else {\n                sub[getGreatestSmallerOrEqual(num, sub)] = num\n            }\n        }\n        \n        return sub.count\n    }\n    \n    // Time: O(logn)\n    // Space: O(1)\n    func getGreatestSmallerOrEqual(_ target: Int, _ arr: [Int]) -> Int {\n        var lo = 0\n        var hi = arr.count - 1\n        while lo < hi {\n            let mi = lo + (hi - lo) / 2\n            if arr[mi] <= target {\n                lo = mi + 1\n            } else {\n                hi = mi\n            }\n        }\n        return lo\n    }\n    \n    // Time: O(k * nlogn)\n    // Space: O(n)\n    func kIncreasing(_ arr: [Int], _ k: Int) -> Int {\n        let n = arr.count\n        var ans = 0\n        for i in 0..<k {\n            var j = i\n            var newArr: [Int] = []\n            while j < n {\n                newArr.append(arr[j])\n                j += k\n            }\n            ans += (newArr.count - lengthOfLNDS(newArr))\n        }\n        return ans\n    }\n}\n```
[]