Rust | LIS
Intuition\n\nSeparate the vector into k subvectors that have no businees with each other.\n\n# Approach\n\nSee Longest Increasing Subsequence. Tho this question
# Intuition\n\nSeparate the vector into `k` subvectors that have no businees with each other.\n\n# Approach\n\nSee [Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/). Tho this question requires longest nondecreasing subsequence, so a bit of modification is needed.\n\n# Complexity\n- Time complexity:\n$$O(n \\log n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\npub fn longest_nondec_subseq(vec: Vec<i32>) -> usize {\n    let mut stack = vec![]; // monotonic stack\n    for e in vec {\n        let e_max = if let Some(inner) = stack.last() {\n            *inner\n        } else {\n            stack.push(e);\n            continue;\n        };\n\n        if e >= e_max {\n            stack.push(e);\n            continue;\n        }\n\n        let ptr = stack.partition_point(|&_e| _e <= e);\n        stack[ptr] = e;\n    }\n\n    stack.len()\n}\n\nimpl Solution {\n    pub fn k_increasing(vec: Vec<i32>, k: i32) -> i32 {\n        let k = k as usize;\n        let n = vec.len();\n\n        let mut vec_vec = vec![vec![]; k];\n        for (i, e) in vec.into_iter().enumerate() {\n            vec_vec[i % k].push(e);\n        }\n\n        let mut ret = usize::MIN;\n        for vec in vec_vec {\n            ret += vec.len();\n            ret -= longest_nondec_subseq(vec);\n        }\n\n        ret as i32\n    }\n}\n```
['Binary Search', 'Monotonic Stack', 'Rust']