/*
 * @lc app=leetcode.cn id=410 lang=cpp
 *
 * [410] 分割数组的最大值
 */

// @lc code=start
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        long long left = *max_element(nums.begin(), nums.end());
        long long right = accumulate(nums.begin(), nums.end(), 0);
        while (left < right) {
            long long maxSum = left + (right - left) / 2;
            int group = split(nums, maxSum);
            if (group >= m) {
                left = maxSum + 1;
            } else {
                right = maxSum;
            }
        }
        return left;
    }

    int split(vector<int>& nums, long long maxSum) {
        int group = 0;
        long long cur = 0;
        for (int num : nums) {
            if (cur + num <= maxSum) {
                cur += num;
            } else {
                group++;
                cur = num;
            }
        }
        return group;
    }
};
// @lc code=end