AM 1251. Split Array Largest Sum

Description

中文English




Given an array which consists of non-negative integers and an integer m, we are going to 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:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)







Have you met this question in a real interview?  






Example




Example 1:
Input：[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：[1,4,4], m = 3
Output：4
Explanation：
    There is a way to split nums into three subarrays.
    The best way is to split it into [1], [4] and [4],
    where the largest sum among the three subarrays is only 4.



这个题最优解法是binary search这里用DP。参考网上的note


算法：

最直观方法是用dfs。我们遍历所有的position，把array划分成两部分，然后左边部分可以直接求和，右边部分再调用helper()去得到一个最小值。然后整个array划分的结果就是max(left, right)。最后我们遍历所有划分，得到一个最小值即可。
对dfs可以使用memo优化性能。复杂度是o(mn)
对于这种min(max())，然后给定了要划分成多少个部分的题目，这是一个典型的binary search answer类型的题目。我们可以任意猜一个答案v，然后看使用v，能否对array进行有效的m个split。如果使用v进行cut得到的subarray个数大于m，说明v太小，我们让low = mid；反之我们让high = mid。最后验证low是否符合要求。如果不符合，那么返回high。


实现：

solution 1使用dfs
slution 2使用二分查找。注意check()里面要判断如果v直接小于nums里面的一个数，说明v是一个invalid的值，直接返回一个max value (line 43 - 44)
？考虑如何把dfs转化为dp，然后看能否进一步优化。。。


复杂度：
dfs: o(mn)
binary search: o(slogs)
class Solution {
public:
    /**
     * @param nums: a list of integers
     * @param m: an integer
     * @return: return a integer
     */
    int splitArray(vector<int> &nums, int m) {
        // write your code here
        const int size = nums.size();
        vector<vector<int>> dp(m + 1, vector<int>(size + 1, INT_MAX)); 
        dp[0][0] = 0; 
        vector<int> prefixSum(size + 1, 0);
        for(int i = 1; i <= size; i++){
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1]; 
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= size; j++){
                for(int k = j - 1; k >= i - 1; k --){
                    int val = max(dp[i - 1][k], prefixSum[j] - prefixSum[k]);
                    dp[i][j] = min(dp[i][j], val); 
                }
            }
        }
        return dp[m][size]; 
    }
};

1