# 0410. Split Array Largest Sum
###### tags: `Leetcode` `Hard` `Dynamic Programming` `Binary Search`
Link: https://leetcode.com/problems/split-array-largest-sum/
## 思路
### DP
### Binary Search By Value
进行```m```的二分搜索，```m```就是代表```nums```分成```k```份后最大自区段的和。 分析：```m```的最小值是```nums```里的最大值；```m```的最大值是数组元素的总和；对于任一个```mid```，另写函数判断是否满足要求。满足要求的话，就继续缩小k来尝试。

如何判断```m```是否可行呢？两个判据：

如果任何```nums[i]>m```，则不可行。
尽可能地合并元素，使得任何子区段的和都不超过```m```，并在遍历的过程中记录这些子区段的数目，超过```k```的话就说明不可行。
## Code
### DP

class Solution {
    public int splitArray(int[] nums, int K) {
        int n = nums.length;
        int[][] dp = new int[n+1][K+1];
        for(int i=1; i<=n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
        for(int i=1; i<=n; i++){
            for(int k=1; k<=Math.min(K, i); k++){
                int sum = 0;
                for(int j=i; j>=k; j--){
                    sum += nums[j-1];
                    dp[i][k] = Math.min(dp[i][k], Math.max(dp[j-1][k-1], sum));
                }
            }
        }
        return dp[n][K];
    }
}

c++

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[] arr = new int[n+1];
        for(int i=0; i<n; i++) arr[i+1] = nums[i];
        for(int i=1; i<=n; i++) arr[i] += arr[i-1];
        
        int[][] dp = new int[n+1][m+1];
        for(int i=1; i<=n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
        for(int i=1; i<=n; i++){
            for(int k=1; k<=Math.min(m, i); k++){
                for(int j=i; j>=k; j--){
                    dp[i][k] = Math.min(dp[i][k], Math.max(dp[j-1][k-1], arr[i]-arr[j-1]));
                }
            }
        }
        return dp[n][m];
    }
}

### Binary Search By Value

class Solution {
    public int splitArray(int[] nums, int k) {
        int start = 0, end = 0;
        for(int num:nums){
            start = Math.max(start, num);
            end += num;
        }
        while(start<end){
            int mid = start+(end-start)/2;
            if(split(nums, mid)>k){
                start = mid+1;
            }
            else end = mid;
        }
        return start;
    }
    public int split(int[] nums, int m){
        int cnt = 0;
        for(int i=0; i<nums.length; i++){
            int cur = 0;
            int j=i;
            while(j<nums.length && cur+nums[j]<=m){
                cur += nums[j++];
            }
            i = j-1;
            cnt++;
        }
        return cnt;
    }
}