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.
If n is the length of array, assume the following constraints are satisfied:
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.
Check all possible splitting plans to find the minimum largest value for subarrays.\n
We can use depth-first search to generate all possible splitting plan. For each element in the array, we can choose to append it to the previous subarray or start a new subarray starting with that element (if the number of subarrays does not exceed
m). The sum of the current subarray can be updated at the same time.
Time complexity : . To split
n elements into
m parts, we can have different solutions. This is equivalent to .
Space complexity : . We only need the space to store the array.\n
The problem satisfies the non-aftereffect property. We can try to use dynamic programming to solve it.\n
The non-aftereffect property means, once the state of a certain stage is determined, it is not affected by the state in the future. In this problem, if we get the largest subarray sum for splitting
j parts, this value will not be affected by how we split the remaining part of
To know more about non-aftereffect property, this link may be helpful : http://www.programering.com/a/MDOzUzMwATM.html\n
f[i][j] to be the minimum largest subarray sum for splitting
jth subarray. We can split the array from a smaller index
i to form it. Thus
f[i][j] can be derived from
max(f[k][j - 1], nums[k + 1] + ... + nums[i]). For all valid index
f[i][j] should choose the minimum value of the above formula.
The final answer should be
n is the size of the array.
For corner situations, all the invalid
f[i][j] should be assigned with
f should be initialized with
Time complexity : . The total number of states is . To compute each state
f[i][j], we need to go through the whole array to find the optimum
k. This requires another loop. So the total time complexity is .
Space complexity : . The space complexity is equivalent to the number of states, which is .\n
We can easily find a property for the answer:\n
If we can find a splitting method that ensures the maximum largest subarray sum will not exceed a value\n
x, then we can also find a splitting method that ensures the maximum largest subarray sum will not exceed any value
ythat is greater than
Lets define this property as
F(x) for the value
F(x) is true means we can find a splitting method that ensures the maximum largest subarray sum will not exceed
From the discussion above, we can find out that for
x ranging from
F(x) will start with false, then from a specific value
F(x) will turn to true and stay true forever.
Obviously, the specific value
x0 is our answer.
We can use Binary search to find the value
x0. Keeping a value
mid = (left + right) / 2. If
F(mid) is false, then we will search the range
[mid + 1, right]; If
F(mid) is true, then we will search
[left, mid - 1].
For a given
x, we can get the answer of
F(x) using a greedy approach. Using an accumulator
sum to store the sum of the current processing subarray and a counter
cnt to count the number of existing subarrays. We will process the elements in the array one by one. For each element
sum + num <= x, it means we can add
num to the current subarray without exceeding the limit. Otherwise, we need to make a cut here, start a new subarray with the current element
num. This leads to an increment in the number of subarrays.
After we have finished the whole process, we need to compare the value
cnt to the size limit of subarrays
cnt <= m, it means we can find a splitting method that ensures the maximum largest subarray sum will not exceed
F(x) should be false.
Time complexity : . The binary search costs , where
sum of array is the sum of elements in
nums. For each computation of
F(x), the time complexity is since we only need to go through the whole array.
Space complexity : . Same as the Brute Force approach. We only need the space to store the array.\n