설명

예 1:

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.

예 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9

예 3:

Input: nums = [1,4,4], m = 3
Output: 4

제약:

솔루션

솔루션 1

직관

암호

class Solution {
public:
    bool check(vector<int>& nums, int m, int largest) {
        int sum = 0, cnt = 0;
        for (int x : nums) {
            if (x > largest) return false;
            if (sum + x > largest) {
                sum = x;
                cnt++;
            } else {
                sum += x;
            }
        }
        if (sum >= 0) cnt++;
        return cnt <= m;
    }
    int splitArray(vector<int>& nums, int m) {
        int l = 0, r = INT_MAX, mid;
        while (l < r) {
            mid = l + r >> 1;
            if (check(nums, m, mid))
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
};

복잡성