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;
    }
};

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];
    }
}

############

class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0, right = 0;
        for (int x : nums) {
            left = Math.max(left, x);
            right += x;
        }
        while (left < right) {
            int mid = (left + right) >> 1;
            if (check(nums, mid, k)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean check(int[] nums, int mx, int k) {
        int s = 1 << 30, cnt = 0;
        for (int x : nums) {
            s += x;
            if (s > mx) {
                ++cnt;
                s = x;
            }
        }
        return cnt <= k;
    }
}

// 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:
    def splitArray(self, nums: List[int], m: int) -> int:
        def check(x):
            s, cnt = 0, 1
            for num in nums:
                if s + num > x:
                    cnt += 1
                    s = num
                else:
                    s += num
            return cnt <= m

        left, right = max(nums), sum(nums)
        while left < right:
            mid = (left + right) >> 1
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

############

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

func splitArray(nums []int, k int) int {
	left, right := 0, 0
	for _, x := range nums {
		left = max(left, x)
		right += x
	}
	return left + sort.Search(right-left, func(mx int) bool {
		mx += left
		s, cnt := 1<<30, 0
		for _, x := range nums {
			s += x
			if s > mx {
				s = x
				cnt++
			}
		}
		return cnt <= k
	})
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

function splitArray(nums: number[], k: number): number {
    let left = 0;
    let right = 0;
    for (const x of nums) {
        left = Math.max(left, x);
        right += x;
    }
    const check = (mx: number) => {
        let s = 1 << 30;
        let cnt = 0;
        for (const x of nums) {
            s += x;
            if (s > mx) {
                s = x;
                ++cnt;
            }
        }
        return cnt <= k;
    };
    while (left < right) {
        const mid = (left + right) >> 1;
        if (check(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

410 - Split Array Largest Sum

410. Split Array Largest Sum (Hard)

Solution 1. DP

Solution 2. DP

Solution 3. DP + Space Optimization

Solution 4. Binary Answer

All Problems

All Solutions

Welcome to Subscribe On Youtube

410. Split Array Largest Sum (Hard)

Solution 1. DP

Solution 2. DP

Solution 3. DP + Space Optimization

Solution 4. Binary Answer

All Problems

All Solutions