410. Split Array Largest Sum

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

• dynamic programming solution
• Time : O(n^2 * m)
• Space : O(nm)

c++

//prefix sum - o(n) - do not need. calculate immediately
//dp from - to o(n^2 * m)
//select minimum
//1 ... 1000 length
//0 ... 1000000 nums
class Solution {
    int dp[1001][50];
    int solution(vector<int>& nums, int l, int m) {
        if(dp[l][m] != -1) return dp[l][m]; //if already calculated
        if(!m) return dp[l][m] = accumulate(nums.begin() + l, nums.end(), 0); //do not need to devide, so add all
        int res = INT_MAX, sum = 0; //init
        for(int i = l; i < nums.size() - m; i++) {
            sum += nums[i];
            res = min(res,max(sum,solution(nums, i + 1, m - 1))); //compare minimum max value before and current max value
        }
        return dp[l][m] = res;
    }
public:
    int splitArray(vector<int>& nums, int m) {
        memset(dp,-1,sizeof(dp));
        return solution(nums,0,m-1);
    }
};

• binary search
• Time : O(nlogn)
• Space : O(1)

c++

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int sum = accumulate(nums.begin(), nums.end(),0);
        if(m == 1) return sum;
        int l = *max_element(nums.begin(), nums.end()), r = sum;
        while(l <= r) {
            int mid = l + (r-l) / 2;
            
            if(verifyArraySplitUnderM(nums, mid, m)) r = mid - 1;
            else l = mid + 1;
            
        }
        return l;
    }
    bool verifyArraySplitUnderM(vector<int>& nums, int mid, int m) {
        int sum = 0;
        for(auto& num : nums) {
            sum += num;
            if(sum > mid) {
                sum = num;
                m--;
                if(!m) return false;
            }
        }
        return true;
    }
};