410

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int low, high, sum;
        sum = low = 0;
        for(auto &num : nums){
            sum += num;
            low = max(low, num);
        }
        high = sum;

        while(low < high){
            int mid = (low+high+1)/2;
            int cuts = 0;
            sum = 0;
            for(auto &num : nums){
                sum += num;
                if(sum >= mid){
                    sum = num;
                    cuts++;
                }
                if(cuts == m) break;
            }

            if(cuts < m)
                high = mid-1;
            else
                low = mid;
        }
        return low;
    }
};