LeetCode [410] Split Array Largest Sum

 410. Split Array Largest Sum

Hard

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

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

 

Constraints:

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

class Solution { public int splitArray(int[] nums, int m) { long l = 0, r = 0; for(long n : nums) { l = Math.max(l, n); r += n; } while(l<r) { long mid = l+(r-l)/2; if(valid(nums, mid, m)) { r = mid; }else{ l = mid+1; } } //r is always valid because 1) it is valid to start with 2) it is always valid on each step //upon exit, l==r because while(l<r). l=3, r=4, mid = 3 ==> l=mid+1=4==r return (int)r; } //return true if min-max <= target boolean valid(int[] nums, long target, int m) { int count = 0; long total = 0; for(long n:nums) { if(total+n<=target){ total += n; }else{ count++; if(count>m) return false; total = n; } } if(total>0) count++; return count<=m; } }