Java Binary Search+DP solution


  • 0
    H

    This question is asking about minimizing the largest sum among these m subarrays, which can be converted to make the sum of each subarray be similar, which is similar to pigeon hole problem in some ways.

    There are many explanation about binary search, so I will focus on dp solution.

    public class Solution {
        public int splitArray(int[] nums, int m) {
            if(nums.length==0) return 0;
            int max=0, sum=0;
            for(int i=0;i<nums.length;i++){
                max=Math.max(max,nums[i]);
                sum+=nums[i];
            }
            int lo=max, hi=sum;
            while(lo<hi){
                int mid=lo+(hi-lo)/2;
                int count=1;
                int target=0;
                boolean valid=false;
                for(int i=0;i<nums.length;i++){
                    target+=nums[i];
                    if(target>mid){
                        target=nums[i];
                        count++;
                        if(count>m) valid=true;
                    }
                }
                if(valid) lo=mid+1;
                else hi=mid;
            }
            return lo;
        }
    }
    

    For DP solution, one way to understand it easily is using the recursive function:

    split = Math.max(sum, splitArray(nums, m - 1, i + 1));
    

    Note that the recursive function returns the answer of array starts from i+1 when it is split into m-1 subarrays.

    public class Solution {
        public int splitArray(int[] nums, int m) {
            if(nums.length==0) return 0;
            long[] dp=new long[nums.length];
            long[] sum=new long[nums.length];
            long s1=0;
            for(int i=0;i<nums.length;i++){
                if(i==0) dp[i]+=(long)nums[i];
                else dp[i]=dp[i-1]+(long)nums[i];
                s1+=(long)nums[i];
                sum[i]=s1;
            }
            for(int s=1;s<m;s++){
                for(int i=nums.length-1;i>=s;i--){
                    for(int j=i-1;j>=s-1;j--){ 
                        long t=Math.max(dp[j],sum[i]-sum[j]);
                        dp[i]=Math.min(dp[i],t);
                    }
                }
            }
            return (int)dp[nums.length-1];
        }
    }
    

Log in to reply
 

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