410. Split Array Largest Sum.md

410. Split Array Largest Sum

---

leetcode-cn Daily Challenge on July 26th, 2020.

---

Difficulty : Hard

Related Topics : Binary Search、Dynamic Programming

---

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.

---

Solution

• mine
  • Java
    • BinarySearch Runtime: 1 ms, faster than 71.83%, Memory Usage: 36.9 MB, less than 57.35% of Java online submissions

      // O(N * D)time   D = sum(nums) - max(nums)
      // O(1)space
      public int splitArray(int[] nums, int m) {
          int n = nums.length;
          long l = 0, r = 0;
          for (int num : nums) {
              l = Math.max(l, num);
              r += num;
          }
          long res = 0;
          while (l < r) {
              res = 0;
              long mid = (l + r) >> 1;
              int t = 1;
              long sum = 0;
              for (int i = 0; i < n; i++) {
                  if (sum + nums[i] > mid) {
                      t++;
                      sum = nums[i];
                  } else {
                      sum += nums[i];
                  }
                  res = Math.max(res, sum);
                  if (t > m) {
                      break;
                  }
              }
              if (t > m) {
                  l = mid + 1;
                  res = l;
              } else {
                  r = mid;
              }
          }
          return (int) res;
      }
      

---

• leetcode solution

• DP Runtime: 39 ms, faster than 21.72%, Memory Usage: 37.3 MB, less than 11.11% of Java online submissions

  // O(N^2 * M)time
  // O(N * M) space
  public int splitArray(int[] nums, int m) {
      int n = nums.length;
      int[][] dp = new int[n + 1][m + 1];
      for (int i = 0; i <= n; i++) {
          Arrays.fill(dp[i], Integer.MAX_VALUE);
      }
      int[] sum = new int[n + 1];
      for (int i = 0; i < n; i++) {
          sum[i + 1] = sum[i] + nums[i];
      }
      dp[0][0] = 0;
      for (int i = 1; i <= n; i++) {
          for (int j = 1; j <= Math.min(i, m); j++) {
              for (int k = 0; k < i; k++) {
                  //dp[k][j - 1] mean k num in the before and split as j-1 
                  dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sum[i] - sum[k]));
              }
          }
      }
      return dp[n][m];
  }
  

---