410. Split Array Largest Sum

410. Split Array Largest Sum

Question

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note: If n is the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Solutions:

• Method 1: DP from top to bottom
  • dp[m][j] means the result from nums[0] to nums[j] into m divisions.
  • we have a index k, where 0 <= k < j.
  • dp[m][j] = min(max(dp[m - 1][k], sum[j] - sum[k]))

     class Solution {
      private int[][] dp;
      private int[] sum;
      public int splitArray(int[] nums, int m) {
          this.sum = new int[nums.length];
          sum[0] = nums[0];
          for(int i = 1; i < nums.length; i++)
              sum[i] = sum[i - 1] + nums[i];
          dp = new int[m + 1][nums.length];
          for(int[] d : dp) Arrays.fill(d, Integer.MAX_VALUE);
          return dfs(m, nums.length - 1);
      }
      // Return the result from nums[0] to nums[j] divided into m parts.
      private int dfs(int m, int j){
          if(m == 1) return sum[j];
          if(m > j + 1) return Integer.MAX_VALUE;
          if(dp[m][j] != Integer.MAX_VALUE) return dp[m][j];
          int res = Integer.MAX_VALUE;
          for(int k = 0; k < j; k++){
              res = Math.min(res, Math.max(sum[j] - sum[k], dfs(m - 1, k)));
          }
          return dp[m][j] = res;
      }
      }
    

• Method 2: from bottom to top

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

• Method 2: Binary Search

    class Solution {
        public int splitArray(int[] nums, int m) {
            long r = 0, l = 0;
            for(int num : nums){
                l = Math.max(l, num);
                r += num;
            }
            r++;
            while(l < r){
                long mid = l + (r - l) / 2;
                int count = 1, temp = 0;
                for(int i = 0; i < nums.length; i++){
                    if(temp + nums[i] > mid){
                        count++;
                        temp = nums[i];
                    }else{
                        temp += nums[i];
                    }
                }
                if(count > m) l = mid + 1;
                else r = mid;
            }
            return (int)l;
        }
    }
  

Reference

1. 花花酱 LeetCode 410. Split Array Largest Sum