410. Split Array Largest Sum Hard

1/**
2 * [410] Split Array Largest Sum
3 *
4 * Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.
5 * Write an algorithm to minimize the largest sum among these m subarrays.
6 *  
7 * Example 1:
8 * 
9 * Input: nums = [7,2,5,10,8], m = 2
10 * Output: 18
11 * Explanation:
12 * There are four ways to split nums into two subarrays.
13 * The best way is to split it into [7,2,5] and [10,8],
14 * where the largest sum among the two subarrays is only 18.
15 * 
16 * Example 2:
17 * 
18 * Input: nums = [1,2,3,4,5], m = 2
19 * Output: 9
20 * 
21 * Example 3:
22 * 
23 * Input: nums = [1,4,4], m = 3
24 * Output: 4
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	1 <= nums.length <= 1000
30 * 	0 <= nums[i] <= 10^6
31 * 	1 <= m <= min(50, nums.length)
32 * 
33 */
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/split-array-largest-sum/
37// discuss: https://leetcode.com/problems/split-array-largest-sum/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41impl Solution {
42    pub fn split_array(nums: Vec<i32>, m: i32) -> i32 {
43        0
44    }
45}
46
47// submission codes end
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test_410() {
55    }
56}
57