# Split Array Largest Sum 410

###### tags: `leetcode`,`binarySearch`,`hard`

>ref: https://leetcode.com/problems/split-array-largest-sum/
>
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.

Write an algorithm to minimize the largest sum among these m subarrays.

>Example 1:
Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

>Example 2:
Input: nums = [1,2,3,4,5], m = 2
Output: 9

>Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)

>1.timeResolution:O(log N)\*O\(log(sum_of_array-max)\)

>2. DP待補 [DP](https://leetcode.com/problems/split-array-largest-sum/discuss/931979/Detailed-and-clean-O(n)-time-solution-with-NO-log(sum))

	public int splitArray(int[] nums, int m) {

		// boundary btw 1. the max in nums and 2. sum of nums
		int left = 0;
		int right = 0;

		for (int num : nums) {
			left = Math.max(left, num);
			right += num;
		}

		while (left < right) {

			int med = left + (right - left) / 2;

			int count = 1;

			int sum = 0;

			loop: for (int num : nums) {
				sum += num;
				if (sum > med) {
					count++;
					sum = num;
				}

				if (count > m) {
					break loop;
				}
			}

			if (count > m) {
				left = med + 1;
			} else {
				right = med; //med is examized.
			}

		}

		return left;

	}