// 二分
class Solution {
public:
    int splitArray(const vector<int>& nums, int m) {
        int r = 0, l = 0;
        for(int i = 0; i < nums.size(); ++ i) {
            r += nums[i];
            l = max(l, nums[i]);
        }

        int ret = -1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(check(nums, mid, m)) {
                ret = mid;
                r = mid - 1;
            } else l = mid + 1;
        }
        return ret;
    }

private:
    bool check(const vector<int> &nums, int mid, int m) {
        int cnt = 0, sum = 0;
        for(int i = 0; i < nums.size(); ++ i) {
            if(sum + nums[i] <= mid) {
                sum += nums[i];
            } else {
                ++ cnt;
                sum = nums[i];
            }
        }
        ++ cnt;     // 最后一部分余留的
        return cnt <= m;
    }
};

// dp
class Solution {
public:
    int splitArray(const vector<int>& nums, int m) {
        // dp[i][j] 表示 [0, i] 数, 分成 j 份, 各自和的最小值
        vector<int> preSum;    // 前缀和, preSum[i + 1] 表示 0~i 的和
        for(int i = 0; i < nums.size(); ++ i) {
            if(i == 0) preSum.emplace_back(0);
            preSum.emplace_back(preSum.back() + nums[i]);
        }

        vector<vector<int>> dp(nums.size(), vector<int>(m + 1, INT_MAX));
        for(int i = 0; i < nums.size(); ++ i) {
            for(int j = 1; j <= m; ++ j) {
                // 前 k 个数至少组成 j - 1 份
                for(int k = j - 2; k < i; ++ k) {   // [k + 1, i] 分成一份, preSum[i] - preSum[k], 然后做 1 个单位偏移量
                    if(k == -1) {   // [0, i] 成一组
                        dp[i][j] = preSum[i + 1] - preSum[k + 1];
                        continue;
                    }
                    dp[i][j] = min(dp[i][j], max(dp[k][j - 1], preSum[i + 1] - preSum[k + 1]));
                }
            }
        }
        return dp.back().back();
    }
};