Easy understand m*n*log(n) solution


  • 0
    C

    ...
    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;
        
    }
    

    }


Log in to reply
 

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