410. Split Array Largest Sum

can refer this:

https://leetcode.com/problems/split-array-largest-sum/discuss/161143/Logical-Thinking-with-Code-Beats-99.89

T : O(nlogn), n: range [max of nums , sum of nums]

S: O(1)

class Solution {
    public int splitArray(int[] nums, int m) {
        long max = 0;
        long sum = 0;
        for (int num : nums) {
            max = Math.max(max, num);
            sum += num;
        }
        
        long left = max;
        long right = sum;
        
        while (left < right) {
            long mid = left + (right - left)/2;
            
            if (splitOk(nums, m, mid)) {
                right = mid;    
            } else {
                left = mid+1;
            }
        }
        return (int)left;
    }
    private boolean splitOk(int[] nums, int m, long val) {
        long sum = 0;
        int count = 1; // 一開始就是一組
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum > val) { // 加太多, 超過時
                sum = nums[i]; // 往回退的意思
                count++;
                if (count > m) {
                    return false;
                }
            }
        }
        return true;
    }
}

left + 1 < right style

class Solution {
    public int splitArray(int[] nums, int m) {
        long max = 0;
        long sum = 0;
        for (int num : nums) {
            max = Math.max(max, num);
            sum += num;
        }
        
        long left = max;
        long right = sum;
        
        while (left + 1 < right) {
            long mid = left + (right - left)/2;
            
            if (splitOk(nums, m, mid)) {
                right = mid;    
            } else {
                left = mid;
            }
        }
        if (splitOk(nums, m, left)) {
            return (int)left;
        }
        if (splitOk(nums, m, right)) {
            return (int)right;
        }
        return 0;
    }
    private boolean splitOk(int[] nums, int m, long val) {
        long sum = 0;
        int count = 1; // 一開始就是一組
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum > val) { // 加太多, 超過時
                sum = nums[i]; // 往回退的意思
                count++;
                if (count > m) {
                    return false;
                }
            }
        }
        return true;
    }
}

DP

T: O(mnk)

S: O(mn)

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        
        long[] presum = new long[n+1];
        for (int i = 1; i <= nums.length; i++) {
            presum[i] = nums[i-1] + presum[i-1];
        }
        
        long[][] dp = new long[m+1][n+1];
        for (int i = 0; i <= m; i++) { // 幾組
            for (int j = 0; j <= n; j++) {
                dp[i][j] = Long.MAX_VALUE; // init max
            }
        }
        dp[0][0] = 0;
        
        for (int i = 1; i <= m; i++) { // 幾組
            for (int j = 1; j <= n; j++) { // 前幾個
                for (int k = i-1; k < j; k++) {
                    long largest = Math.max(dp[i-1][k], presum[j] - presum[k]);
                    dp[i][j] = Math.min(dp[i][j], largest);
                }
            }
        }
        return (int)dp[m][n];
    }
}