410. Split Array Largest Sum

  • 34.2%

https://leetcode.com/problems/split-array-largest-sum/?tab=Description

Given an array 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.

Note:

If n is the length of array, assume the following constraints are satisfied:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)
1
2
3
4
5
6
7
8
9
10
11
12
13
Examples:

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.

方法一:

https://discuss.leetcode.com/topic/61395/c-fast-very-clear-explanation-clean-code-solution-with-greedy-algorithm-and-binary-search

[C++ / Fast / Very clear explanation / Clean Code] Solution with Greedy Algorithm and Binary Search

First thing first, below is the code:

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
class Solution {
private:
bool doable (const vector<int>& nums, int cuts, long long max) {
int acc = 0;
for (num : nums) {
// This step is unnecessary for this problem. I didn't discard this line because I want doable function more generalized.
if (num > max) return false;
else if (acc + num <= max) acc += num;
else {
--cuts;
acc = num;
if (cuts < 0) return false;
}
}
return true;
}

public:
int splitArray(vector<int>& nums, int m) {
long long left = 0, right = 0;
for (num : nums) {
left = max(left, (long long)num);
right += num;
}

while (left < right) {
long long mid = left + (right - left) / 2;
if (doable(nums, m - 1, mid)) right = mid;
else left = mid + 1;
}
return left;
}
};

Introduction to this problem:

We can break this problem into two smaller problems:

  • Given an array (A), number of cuts (CUTS), and the Largest sum of sub-arrays (MAX). Can you use at most CUTS cuts to segment array A into CUTS + 1 sub-arrays, such that the sum of each sub-array is smaller or equal to MAX?
  • Given a lower bound (left), an upper bound (right), an unknown bool array (B), and an API uses i as input and tells you whether B[i] is true. If we know there exists an index k, that B[i] is false when i < k, and B[i] is true when i >= k. What is the fastest way to find this k (the lower bound)?
    Solution to the first sub-problem (Skip this part if you already knew how to solve 1st sub-problem):

For the first question, we can follow these steps:

  • For each element in the array, if its value is larger than MAX, we know it’s not possible to cut this array into groups that the sum of all groups are smaller than MAX. (Reason is straightforward, if A is [10, 2, 3, 5] and MAX is 6, even you have 3 cuts by which you can cut A as [[10], [2], [3], [5]], the group containing 10 will still be larger than 6).
  • Use greedy algorithm to cut A. Use an accumulator ACC to store the sum of the currently processed group, and process elements in A one by one. For each element num, if we add num with ACC and the new sum is still no larger than MAX, we update ACC to ACC + num, which means we can merge num into the current group. If not, we must use a cut before num to segment this array, then num will be the first element in the new group.
  • If we didn’t go through A but already used up all cuts, then it’s not possible only using CUTS cuts to segment this array into groups to make sure sum of each sub-array is smaller than MAX. Otherwise, if we can reach the end of A with cuts left (or use exactly CUTS cuts). It’s possible to do so.
    Then the first question is solved.

Solution to the second sub-problem(Skip this part if you already knew how to solve 2nd sub-problem):

  • The array B will be something like [false, false, …, false, true, true, …, true]. We want to find the index of the first true.
  • Use binary search to find this k. Keep a value mid, mid = (left + right) / 2. If B[mid] = false, then move the search range to the upper half of the original search range, a.k.a left = mid + 1, otherwise move search range to the lower half, a.k.a right = mid.
    Why this algorithm is correct…

  • No matter how we cut the array A, the Largest sum of sub-arrays will fall into a range [left, right]. Left is the value of the largest element in this array. right is the sum of this array. (e.g., Given array [1, 2, 3, 4, 5], if we have 4 cuts and cut it as [[1], [2], [3], [4], [5]], the Largest sum of sub-arrays is 5, it cannot be smaller. And if we have 0 cut, and the only sub-array is [[1, 2, 3, 4, 5]], the Largest sum of sub-arrays is 15, it cannot be larger).

  • However, we cannot decide the number of cuts (CUTS), this is an given constraint. But we know there must be a magic number k, which is the smallest value of the Largest sum of sub-arrays when given CUTS cuts. When the Largest sum of sub-arrays is larger than k, we can always find a way to cut A within CUTS cuts. When the Largest sum of sub-arrays is smaller than k, there is no way to do this.
    Example

For example, given array A [1, 2, 3, 4, 5]. We can use 2 cuts.

  • o matter how many cuts are allowed, the range of the possible value of the Largest sum of sub-arrays is [5, 15].
  • When given 2 cuts, we can tell the magic number k here is 6, the result of segmentation is [[1, 2, 3], [4], [5]].
  • When Largest sum of sub-arrays is in range [6, 15], we can always find a way to cut this array within two cuts. You can have a try.
  • However, when Largest sum of sub-arrays is in range [5, 5], there is no way to do this.
  • This mapped this problem into the second sub-problem. Bool array B here is [5:false, 6:true, 7:true, 8:true, …, 15:true]. We want to find the index i of the first true in B, which is the answer of this entire question, and by solving the first sub-problem, we have an API that can tell us given an i (Largest sum of sub-arrays), whether B[i] is true (whether we can find a way to cut A to satisfy the constraint).
    Below is the code with comment, just in case you don’t have time to read the explanations above.
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
private:
/*
Params:
nums - The input array;
cuts - How many cuts are available (cuts = #groups - 1);
max - The maximum of the (sum of elements in one group);
Rtn:
Whether we can use at most 'cuts' number of cuts to segment the entire array,
such that the sum of each group will not exceed 'max'.
*/
bool doable (const vector<int>& nums, int cuts, long long max) {

// 'acc' is the temporary accumulator for the currently processed group.

int acc = 0;
for (num : nums) {

// If the current processed element in this array is larger than 'max', we cannot segment the array.
// (Reason is straightforward, if 'nums' is [10, 2, 3, 5] and 'max' is 6, even you can have 3 cuts
// (by which you can cut array as [[10], [2], [3], [5]]), the group containing 10 will be larger than 6,
// there is no way to do this).
// Ps: This step is unnecessary in this solution. Because 'left' in the splitArray() function can assure
// 'max' will be larger than every single element. I just want to write a generalized doable() function :)

if (num > max) return false;

// If the (sum of the currently processed group) + (current element) is smaller than max, we can add current
// element into this group.

else if (acc + num <= max) acc += num;

// If not, we will make a cut before this element, and this element will be the first element in the new group.

else {
--cuts;
acc = num;

// If we've used up all cuts, this means this 'max' is not doable.
if (cuts < 0) return false;
}
}

// If we can reach here, this means we've used at most 'cuts' cut to segment the array, and the sum of each groups is
// not larger than 'max'. Yeah!
return true;
}

public:
int splitArray(vector<int>& nums, int m) {
// Use long long to avoid overflow.
long long left = 0, right = 0;
// The smallest possible value ('left') is the the value of the largest element in this array.
// The largest possible value ('right') is the sum of all elements in this array.
for (num : nums) {
left = max(left, (long long)num);
right += num;
}

// Use binary search, find the lower bound of the possible (minimum sum of groups within m - 1 cuts).
while (left < right) {
long long mid = left + (right - left) / 2;
if (doable(nums, m - 1, mid)) right = mid;
else left = mid + 1;
}
return left;
}
};

https://discuss.leetcode.com/topic/61314/binary-search-c-solution

Binary Search C++ Solution

Obviously, the final result is in the interval [left, right] (where left is the maximal number in the array, right is sum of all numbers).
So, what we need to do is to find out the first element in [left, right], which exactly we cannot split the array into m subarrays whose sum is no greater than that element. Then its previous one is the final result. The progress is much similar to lower_bound in 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
class Solution {
public:
using ll = long long;

bool canSplit(vector<int>& nums, int m, ll sum) {
int c = 1;
ll s = 0;
for (auto& num : nums) {
s += num;
if (s > sum) {
s = num;
++c;
}
}
return c <= m;
}

int splitArray(vector<int>& nums, int m) {
ll left = 0, right = 0;
for (auto& num : nums) {
left = max(left, (ll)num);
right += num;
}
while (left <= right) {
ll mid = left + (right-left)/2;
if (canSplit(nums, m, mid))
right = mid-1;
else
left = mid+1;
}
return left;
}
};

python


https://discuss.leetcode.com/topic/62139/python-solution-dp-and-binary-search

Python solution dp and binary search

First i try dp, while got TLE:(while if using java to implement dp, u may get AC…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
dp = [[sys.maxint]*(m) for _ in range(len(nums)+1)]
acc = 0
dp[0][0] = 0
for i in range(1, len(nums)+1):
acc += nums[i - 1]
dp[i][0] = acc

for j in range(m):
dp[0][j] = 0

for i in range(1, len(nums)+1):
for i_ in range(i):
for j in range(1, m):
dp[i][j] = min(dp[i][j], max(dp[i_][j-1], dp[i][0]-dp[i_][0]))
#print dp
return dp[len(nums)][m-1]

Then by binary search, got AC:

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
class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
def valid(mid):
cnt = 0
current = 0
for n in nums:
current += n
if current>mid:
cnt += 1
if cnt>=m:
return False
current = n
return True

l = max(nums)
h = sum(nums)

while l<h:
mid = l+(h-l)/2
if valid(mid):
h = mid
else:
l = mid+1
return l

java


https://discuss.leetcode.com/topic/61324/clear-explanation-8ms-binary-search-java

Clear Explanation: 8ms Binary Search Java

  1. The answer is between maximum value of input array numbers and sum of those numbers.
  2. Use binary search to approach the correct answer. We have l = max number of array; r = sum of all numbers in the array;Every time we do mid = (l + r) / 2;
  3. Use greedy to narrow down left and right boundaries in binary search.
    • 3.1 Cut the array from left.
    • 3.2 Try our best to make sure that the sum of numbers between each two cuts (inclusive) is large enough but still less than mid.
    • 3.3 We’ll end up with two results: either we can divide the array into more than m subarrays or we cannot.

If we can, it means that the mid value we pick is too small because we’ve already tried our best to make sure each part holds as many non-negative numbers as we can but we still have numbers left. So, it is impossible to cut the array into m parts and make sure each parts is no larger than mid. We should increase m. This leads to l = mid + 1;
If we can’t, it is either we successfully divide the array into m parts and the sum of each part is less than mid, or we used up all numbers before we reach m. Both of them mean that we should lower mid because we need to find the minimum one. This leads to r = mid - 1;

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
public class Solution {
public int splitArray(int[] nums, int m) {
int max = 0; long sum = 0;
for (int num : nums) {
max = Math.max(num, max);
sum += num;
}
if (m == 1) return (int)sum;
//binary search
long l = max; long r = sum;
while (l <= r) {
long mid = (l + r)/ 2;
if (valid(mid, nums, m)) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return (int)l;
}
public boolean valid(long target, int[] nums, int m) {
int count = 1;
long total = 0;
for(int num : nums) {
total += num;
if (total > target) {
total = num;
count++;
if (count > m) {
return false;
}
}
}
return true;
}
}

list item


https://discuss.leetcode.com/topic/61405/dp-java

DP Java

DP solution. This is obviously not as good as the binary search solutions; but it did pass OJ.

dp[s,j] is the solution for splitting subarray n[j]…n[L-1] into s parts.

dp[s+1,i] = min{ max(dp[s,j], n[i]+…+n[j-1]) }, i+1 <= j <= L-s

This solution does not take advantage of the fact that the numbers are non-negative (except to break the inner loop early). That is a loss. (On the other hand, it can be used for the problem containing arbitrary numbers)

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
public int splitArray(int[] nums, int m)
{
int L = nums.length;
int[] S = new int[L+1];
S[0]=0;
for(int i=0; i<L; i++)
S[i+1] = S[i]+nums[i];

int[] dp = new int[L];
for(int i=0; i<L; i++)
dp[i] = S[L]-S[i];

for(int s=1; s<m; s++)
{
for(int i=0; i<L-s; i++)
{
dp[i]=Integer.MAX_VALUE;
for(int j=i+1; j<=L-s; j++)
{
int t = Math.max(dp[j], S[j]-S[i]);
if(t<=dp[i])
dp[i]=t;
else
break;
}
}
}

return dp[0];
}

https://discuss.leetcode.com/topic/61315/java-easy-binary-search-solution-8ms

Java easy binary search solution 8ms

  • Given a result, it is easy to test whether it is valid or not.
  • The max of the result is the sum of the input nums.
  • The min of the result is the max num of the input nums.

Given the 3 conditions above we can do a binary search. (need to deal with overflow)

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
public class Solution {
public int splitArray(int[] nums, int m) {
long sum = 0;
int max = 0;
for(int num: nums){
max = Math.max(max, num);
sum += num;
}
return (int)binary(nums, m, sum, max);
}

private long binary(int[] nums, int m, long high, long low){
long mid = 0;
while(low < high){
mid = (high + low)/2;
if(valid(nums, m, mid)){
//System.out.println(mid);
high = mid;
}else{
low = mid + 1;
}
}
return high;
}

private boolean valid(int[] nums, int m, long max){
int cur = 0;
int count = 1;
for(int num: nums){
cur += num;
if(cur > max){
cur = num;
count++;
if(count > m){
return false;
}
}
}
return true;
}
}
谢谢你,可爱的朋友。