410. Split Array Largest Sum

Posted on Edited on In

410. Split Array Largest Sum

Description

Difficulty: Hard

Related Topics: Array, Binary Search, Dynamic Programming, Greedy

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.

Return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

Example 1:

1
2
3
4
Input: nums = [7,2,5,10,8], k = 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:

1
2
3
4
Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.

Constraints:

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

Hints/Notes

  • Read the problem: A subarray is a contiguous part of the array.
  • Use binary search and helper function to find the left boundary

Solution

Language: C++

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
class Solution {
public:
    int subarrayNum(vector<int>& nums, int s) {
        int num = 0;
        for (int i = 0; i < nums.size();) {
            int sum = 0;
            while (sum <= s && i < nums.size()) {
                sum += nums[i++];
            }
            if (sum > s) {
                i--;
            }
            num++;
        }
        return num;
    }

    int splitArray(vector<int>& nums, int k) {
        int left = 0, right = 0;
        for (int num : nums) {
            if (num > left) {
                left = num;
            }
            right += num;
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int subNum = subarrayNum(nums, mid);
            if (subNum == k) {
                right = mid - 1;
            } else if (subNum > k) {
                left = mid + 1;
            } else if (subNum < k) {
                right = mid - 1;
            }
        }
        return left;
    }
};