Straightforward java dp solution


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

Log in to reply
 

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