Formatted question description: https://leetcode.ca/all/410.html

410. Split Array Largest Sum (Hard)

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.

Companies:
Google

Related Topics:
Binary Search, Dynamic Programming

Solution 1. DP

Let dp[m][i] be the answer to the subproblem with m subarrays within A[0..i].

Let sum[i][j] be the sum of numbers in A[i..j].

dp[1][i] = sum[0][i]
dp[k][i] = min(max(dp[k-1][j-1], sum[j][i]) | m - 1 <= j <= i)
// OJ: https://leetcode.com/problems/split-array-largest-sum/
// Time: O(N^2 * M)
// Space: O(N^2 + NM)
class Solution {
    typedef long long LL;
public:
    int splitArray(vector<int>& A, int M) {
        int N = A.size();
        vector<vector<LL>> sum(N, vector<LL>(N, 0)), dp(M + 1, vector<LL>(N, INT_MAX));
        for (int i = 0; i < N; ++i) {
            LL s = 0;
            for (int j = i; j < N; ++j) {
                sum[i][j] = (s += A[j]);
            }
        }
        for (int i = 0; i < N; ++i) dp[1][i] = sum[0][i];
        for (int m = 2; m <= M; ++m) {
            for (int i = m - 1; i < N; ++i) {
                for (int j = m - 1; j <= i; ++j) {
                    dp[m][i] = min(dp[m][i], max(dp[m - 1][j - 1], sum[j][i]));
                }
            }
        }
        return dp[M][N - 1];
    }
};

Solution 2. DP

We can compute sum on the fly.

// OJ: https://leetcode.com/problems/split-array-largest-sum/
// Time: O(N^2 * M)
// Space: O(NM)
class Solution {
    typedef long long LL;
public:
    int splitArray(vector<int>& A, int M) {
        int N = A.size();
        vector<vector<LL>> dp(M + 1, vector<LL>(N, INT_MAX));
        LL s = 0;
        for (int i = 0; i < N; ++i) dp[1][i] = (s += A[i]);
        for (int m = 2; m <= M; ++m) {
            for (int i = m - 1; i < N; ++i) {
                LL sum = 0;
                for (int j = i; j >= m - 1; --j) {
                    sum += A[j];
                    dp[m][i] = min(dp[m][i], max(dp[m - 1][j - 1], sum));
                }
            }
        }
        return dp[M][N - 1];
    }
};

Solution 3. DP + Space Optimization

Given the dp dependency, we can just use 1D dp array.

// OJ: https://leetcode.com/problems/split-array-largest-sum/
// Time: O(N^2 * M)
// Space: O(N)
class Solution {
    typedef long long LL;
public:
    int splitArray(vector<int>& A, int M) {
        int N = A.size();
        vector<LL> dp(N, INT_MAX);
        LL s = 0;
        for (int i = 0; i < N; ++i) dp[i] = (s += A[i]);
        for (int m = 2; m <= M; ++m) {
            for (int i = N - 1; i >= m - 1; --i) {
                LL sum = 0;
                dp[i] = INT_MAX;
                for (int j = i; j >= m - 1; --j) {
                    sum += A[j];
                    dp[i] = min(dp[i], max(dp[j - 1], sum));
                }
            }
        }
        return dp[N - 1];
    }
};

Solution 4. Binary Answer

The answer is between the maximum element and the sum of all the elements.

// OJ: https://leetcode.com/problems/split-array-largest-sum/
// Time: O(N * log(S)) where S is sum of nums.
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/61324/clear-explanation-8ms-binary-search-java
class Solution {
    typedef long long LL;
    int split(vector<int> &A, LL M) {
        LL cnt = 0, sum = 0;
        for (int i = 0; i < A.size(); ++i) {
            sum += A[i];
            if (sum > M) {
                sum = A[i];
                ++cnt;
            }
        }
        return cnt + 1;
    }
public:
    int splitArray(vector<int>& A, int m) {
        LL sum = accumulate(begin(A), end(A), (LL)0);
        if (m == 1) return sum;
        LL L = *max_element(begin(A), end(A)), R = sum;
        while (L <= R) {
            LL M = (L + R) / 2;
            int n = split(A, M);
            if (n <= m) R = M - 1;
            else L = M + 1;
        }
        return L;
    }
};

Java

  • class Solution {
        public int splitArray(int[] nums, int m) {
            int length = nums.length;
            int[][] dp = new int[length + 1][m + 1];
            int[] subSum = new int[length + 1];
            for (int i = 0; i <= length; i++) {
                for (int j = 0; j <= m; j++)
                    dp[i][j] = Integer.MAX_VALUE;
            }
            for (int i = 0; i < length; i++)
                subSum[i + 1] = subSum[i] + nums[i];
            dp[0][0] = 0;
            for (int i = 1; i <= length; i++) {
                for (int j = 1; j <= m; j++) {
                    for (int k = 0; k < i; k++)
                        dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], subSum[i] - subSum[k]));
                }
            }
            return dp[length][m];
        }
    }
    
  • // OJ: https://leetcode.com/problems/split-array-largest-sum/
    // Time: O(N * log(S)) where S is sum of nums.
    // Space: O(1)
    // Ref: https://discuss.leetcode.com/topic/61324/clear-explanation-8ms-binary-search-java
    class Solution {
    public:
        int splitArray(vector<int>& A, int m) {
            long sum = accumulate(begin(A), end(A), 0L);
            if (m == 1) return sum;
            long L = *max_element(begin(A), end(A)), R = sum, N = A.size();
            auto valid = [&](int maxSum) {
                int cnt = 1, i = 0 ;
                for (int sum = 0; i < N && cnt <= m; ++i) {
                    sum += A[i];
                    if (sum > maxSum) {
                        sum = A[i];
                        ++cnt;
                    }
                }
                return i == N && cnt <= m;
            };
            while (L <= R) {
                long M = L + (R - L) / 2;
                if (valid(M)) R = M - 1;
                else L = M + 1;
            }
            return L;
        }
    };
    
  • class Solution(object):
      def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
    
        def valid(nums, target, m):
          count = 1
          total = 0
          for num in nums:
            total += num
            if total > target:
              count += 1
              total = num
              if count > m:
                return False
          return True
    
        start, end = max(nums), sum(nums)
        mid = 0
        while start <= end:
          mid = start + (end - start) / 2
          if valid(nums, mid, m):
            end = mid - 1
          else:
            start = mid + 1
    
        return start
    
    

All Problems

All Solutions