【leetcode】410. Split Array Largest Sum

发表于

描述
给一个数组nums，分成m份，求每一种分法每一份的最大值的最小值。

有点绕，感觉又是组合爆炸。参考这篇文章后，得到了一些启发。将这个题转换成查找问题，不要被最小值迷惑，我们就求最大值，然后向下逼近。最大值的范围在单个数字最大值和总和之间，从总和开始向下枚举计算。要求这个最大值大于所有的子数组，m则为失败的次数条件，显然m越大，这个最大值可以更加的小，失败数目超过m后显然就不成立了，于是题目就解决了。

下面这个解法会超时，时间复杂度为O(N^2)，可以改进为二分查找。

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
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int left = INT_MIN;
        int right = 0;
        for (auto n : nums) {
            if (left < n) { left = n; }
            right += n;
        }
        int result = right;
        for (int i = right; i >= left; i--) {
            int cnt = 1;
            int subsum=0;
            bool done = false;
            for (auto n : nums) {
                subsum += n;
                if (subsum > i) {
                    cnt++;
                    subsum = n;
                    if (cnt > m) {
                        done = true;
                        break;
                    }
                }
            }
            if (done == false) { result = i; }
            else { break; }
        }
        return result;
    }
};

参考资料
题目链接

`