410.Split-Array-Largest-Sum

410. Split Array Largest Sum

题目地址

https://leetcode.com/problems/split-array-largest-sum/

题目描述

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.

代码

Approach #1 Dynamic Programming

Let's define f[i][j] to be the minimum largest subarray sum for splitting nums[0..i] into j parts.

Time: O(N^2 M) && Space: O(NM)

class Solution {
  public int splitArray(int[] nums, int m) {
        int n = nums.length;
    int[][] f = new int[n + 1][m + 1];
    int[] sub = new int[n + 1];
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= m; j++) {
        f[i][j] = Integer.MAX_VALUE;
      }
    }
    for (int i = 0; i < n; i++) {
      sub[i + 1] = sub[i] + nums[i];
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        for (int k = 0; k < i; k++) {
          f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));
        }
      }
    }
    return f[n][m];
  }
}

Approach #2 Binary Search + Greedy

• Set the search range between min=(largest single value) and max=(sum of all values).

  The min starts there because we're looking for the sum of the largest group in the final set of groups. And no matter what groups you create, the largest value has to be in it, so the largest group can't be smaller than that. (This assumes no negative numbers.)

class Solution {
  public int splitArray(int[] nums, int m) {
    long l = 0;
    long r = 0;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
      r += nums[i];
      if (l < nums[i]) {
        l = nums[i];
      }
    }

    long ans = r;
    while (l <= r) {
      long mid = (l + r) >> 1;
      long sum = 0;
      int cnt = 1;
      for (int i = 0; i < n; i++) {
        if (sum + nums[i] > mid) {
          cnt++;
          sum = nums[i];
        } else {
          sum += nums[i];
        }
      }
      if (cnt <= m) {
        ans = Math.min(ans, mid);
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }

    return (int)ans;
  }
}

Approach #0 Brute Force

Time complexity : O(n^m)

Space complexity : O(n)

class Solution {
    private int ans;
    private int n, m;
    private void dfs(int[] nums, int i, int cntSubarrays, int curSum, int curMax) {
        if (i == n && cntSubarrays == m) {
            ans = Math.min(ans, curMax);
            return;
        }
        if (i == n) { 
            return;
        }
        if (i > 0) {
            dfs(nums, i + 1, cntSubarrays, curSum + nums[i], Math.max(curMax, curSum + nums[i]));
        }
        if (cntSubarrays < m) {
            dfs(nums, i + 1, cntSubarrays + 1, nums[i], Math.max(curMax, nums[i]));
        }
    }
    public int splitArray(int[] nums, int M) {
        ans = Integer.MAX_VALUE;
        n = nums.length;
        m = M;
        dfs(nums, 0, 0, 0, 0);
        return ans;
    }
}