# Easy understand m*n*log(n) solution

• ...
public class Solution {
public int splitArray(int[] nums, int m) {
for(int i=1;i<nums.length;i++){
nums[i]=nums[i-1]+nums[i];
}
int [][] dp= new int[m][nums.length];
dp[0][nums.length-1]=nums[nums.length-1];
for(int i=nums.length-1;i>=0;i--){
dp[0][i]=nums[nums.length-1]-(i>0?nums[i-1]:0);

``````    }

for(int k=1;k<m;k++){
for(int i=nums.length-1-k;i>=0;i--){
dp[k][i]=bs(nums,dp,i+1,nums.length-k,k,i);
}
}

return dp[m-1][0];
}

public int bs(int[] nums,int [][] dp, int start,int end,int k,int i){
if(start==end) return Math.max(nums[end-1]-(i>0?nums[i-1]:0),dp[k-1][end]);
if(start+1==end) return Math.min(Math.max(nums[start-1]-(i>0?nums[i-1]:0),dp[k-1][start]),Math.max(nums[end-1]-(i>0?nums[i-1]:0),dp[k-1][end]));

int mid=(start+end)/2;
int res=Math.max(nums[mid-1]-(i>0?nums[i-1]:0),dp[k-1][mid]);
if(nums[mid-1]-(i>0?nums[i-1]:0)>dp[k-1][mid]) res=Math.min(res,bs(nums,dp,start,mid-1,k,i));
else if(nums[mid-1]-(i>0?nums[i-1]:0)<dp[k-1][mid])res=Math.min(res,bs(nums,dp,mid+1,end,k,i));

return res;

}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.