410. Split Array Largest Sum 把数组划分为m组，怎样使最大和最小

［抄题］：

Given an array 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.

Note:
If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

不知道干嘛用二分法：二分法可以通过mid的移动找一个位置

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［一句话思路］：

想不到：最大的数肯定要分隔开，就看能往左划几个数和它一组

[7,2,5,10,8,105550]
3
返回105550

分组不超过m就往左扩展否则往右

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

l r都必须定义成long型，在返回的时候切换回来

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

多试试几个case 自然就明白了

数组中找一个位置，就可以用二分查找

［复杂度］：Time complexity: O(lgn) Space complexity: O(1)

［算法思想：迭代/递归/分治/贪心］：迭代

［关键模板化代码］：

while (l <= r) {
            long mid = (l + r) / 2;
            if (noLongerThanM(mid, nums, m)) r = mid - 1;
            else l = mid + 1;
        }
        
        return (int)l; 
    }

［其他解法］：

dp麻烦

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

class Solution {
    public int splitArray(int[] nums, int m) {
        //ini: sum, l, r
        int max = nums[0]; long sum = 0;
        for (int num : nums) {
            sum += num;
            max = Math.max(max, num);
        }

        //cc
        if (nums.length == 1) return (int)sum;
        long l = max, r = sum;
        
        // b - s
        while (l <= r) {
            long mid = (l + r) / 2;
            if (noLongerThanM(mid, nums, m)) r = mid - 1;
            else l = mid + 1;
        }
        
        return (int)l; 
    }
    
    public boolean noLongerThanM(long value, int[] nums, int m) {
        int count = 1, sum = 0;
        
        for (int num : nums) {
            sum += num;
            if (sum > value) {
                sum = num;
                count++;
                if (count > m) return false;
            }
        }
        
        return true;
    }
}

View Code