rustgym/leetcode/
_410_split_array_largest_sum.rs

1struct Solution;
2
3impl Solution {
4    fn split_array(nums: Vec<i32>, m: i32) -> i32 {
5        let mut lo = *nums.iter().max().unwrap();
6        let mut hi = nums.iter().sum();
7        let n = nums.len();
8        while lo <= hi {
9            let mid = (lo + hi) / 2;
10            if Self::split(&nums, mid, n) <= m {
11                hi = mid - 1;
12            } else {
13                lo = mid + 1;
14            }
15        }
16        lo
17    }
18
19    fn split(nums: &[i32], max: i32, n: usize) -> i32 {
20        let mut sum = 0;
21        let mut res = 1;
22        for i in 0..n {
23            if nums[i] + sum > max {
24                sum = nums[i];
25                res += 1;
26            } else {
27                sum += nums[i];
28            }
29        }
30        res
31    }
32}
33
34#[test]
35fn test() {
36    let nums = vec![7, 2, 5, 10, 8];
37    let m = 2;
38    let res = 18;
39    assert_eq!(Solution::split_array(nums, m), res);
40    let nums = vec![1, 2, 3, 4, 5];
41    let m = 2;
42    let res = 9;
43    assert_eq!(Solution::split_array(nums, m), res);
44    let nums = vec![1, 4, 4];
45    let m = 3;
46    let res = 4;
47    assert_eq!(Solution::split_array(nums, m), res);
48    let nums = vec![2, 3, 1, 2, 4, 3];
49    let m = 5;
50    let res = 4;
51    assert_eq!(Solution::split_array(nums, m), res);
52}
rustgym/leetcode/_410_split_array_largest_sum.rs

rustgym/leetcode/
_410_split_array_largest_sum.rs
