768. Max Chunks To Make Sorted II Hard

1/**
2 * [768] Max Chunks To Make Sorted II
3 *
4 * You are given an integer array arr.
5 * We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.
6 * Return the largest number of chunks we can make to sort the array.
7 *  
8 * Example 1:
9 * 
10 * Input: arr = [5,4,3,2,1]
11 * Output: 1
12 * Explanation:
13 * Splitting into two or more chunks will not return the required result.
14 * For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.
15 * 
16 * Example 2:
17 * 
18 * Input: arr = [2,1,3,4,4]
19 * Output: 4
20 * Explanation:
21 * We can split into two chunks, such as [2, 1], [3, 4, 4].
22 * However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.
23 * 
24 *  
25 * Constraints:
26 * 
27 * 	1 <= arr.length <= 2000
28 * 	0 <= arr[i] <= 10^8
29 * 
30 */
31pub struct Solution {}
32
33// problem: https://leetcode.com/problems/max-chunks-to-make-sorted-ii/
34// discuss: https://leetcode.com/problems/max-chunks-to-make-sorted-ii/discuss/?currentPage=1&orderBy=most_votes&query=
35
36// submission codes start here
37
38impl Solution {
39    pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
40        0
41    }
42}
43
44// submission codes end
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49
50    #[test]
51    fn test_768() {
52    }
53}
54