# Split Array Largest Sum
**Difficulty:** HARD
[External](https://leetcode.com/problems/split-array-largest-sum)
Canonical: https://scaleengineer.com/dsa/problems/split-array-largest-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Tekion](https://scaleengineer.com/companies/tekion), [PornHub](https://scaleengineer.com/companies/pornhub), [Salesforce](https://scaleengineer.com/companies/salesforce), [Zeta](https://scaleengineer.com/companies/zeta), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [PhonePe](https://scaleengineer.com/companies/phonepe), [Pinterest](https://scaleengineer.com/companies/pinterest), [MathWorks](https://scaleengineer.com/companies/mathworks), [Baidu](https://scaleengineer.com/companies/baidu)
---
## Problem
Given an integer array `nums` and an integer `k`, split `nums` into `k` non-empty subarrays such that the largest sum of any subarray is **minimized**.

Return _the minimized largest sum of the split_.

A **subarray** is a contiguous part of the array.

**Example 1:**

**Input:** nums = [7,2,5,10,8], k = 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.

**Example 2:**

**Input:** nums = [1,2,3,4,5], k = 2
**Output:** 9
**Explanation:** There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.

**Constraints:**

* `1 <= nums.length <= 1000`
* `0 <= nums[i] <= 106`
* `1 <= k <= min(50, nums.length)`

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem by breaking it down into smaller, overlapping subproblems. We build a table `dp[i][j]` which stores the minimum largest subarray sum for splitting the first `j` elements of the array into `i` parts. The final answer is found by computing the value for splitting the entire array into `k` parts.
**Time:** O(k * n^2), where `n` is the number of elements and `k` is the number of splits. There are three nested loops to fill the DP table. · **Space:** O(k * n), for the 2D DP table of size `(k+1) x (n+1)` and the prefix sum array of size `n+1`.
**Pros:** It is a systematic approach that guarantees finding the optimal solution.; The logic is relatively straightforward to formulate for those familiar with dynamic programming.
**Cons:** The time complexity of `O(k * n^2)` can be too slow if `n` is large.; The space complexity of `O(k * n)` can be substantial for large `k` and `n`.
### Explanation
In this dynamic programming approach, we define `dp[i][j]` as the minimum largest sum required to split the subarray `nums[0...j-1]` (the first `j` elements) into `i` non-empty subarrays. Our objective is to find `dp[k][n]`, where `n` is the length of `nums`.

The state transition is formulated by considering all possible split points for the last (`i`-th) subarray. If we decide the `i`-th subarray is `nums[p...j-1]`, then the first `p` elements (`nums[0...p-1]`) must have been optimally split into `i-1` subarrays. The largest sum for this specific split would be the maximum of the sum of the last subarray (`sum(nums[p...j-1])`) and the result for the prefix (`dp[i-1][p]`). We want to choose a split point `p` that minimizes this value.

To make the calculation of subarray sums efficient, we pre-compute a prefix sum array. This allows us to find the sum of any subarray in `O(1)` time.

```java
class Solution {
    public int splitArray(int[] nums, int k) {
        int n = nums.length;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        long[][] dp = new long[k + 1][n + 1];
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = Long.MAX_VALUE;
            }
        }
        dp[0][0] = 0;

        for (int i = 1; i <= k; i++) { // Number of subarrays
            for (int j = 1; j <= n; j++) { // Number of elements
                for (int p = 0; p < j; p++) { // Split point
                    long lastSum = prefixSum[j] - prefixSum[p];
                    if (dp[i - 1][p] != Long.MAX_VALUE) {
                        long currentMax = Math.max(dp[i - 1][p], lastSum);
                        dp[i][j] = Math.min(dp[i][j], currentMax);
                    }
                }
            }
        }
        return (int) dp[k][n];
    }
}
```
### Algorithm
- Define a 2D array `dp[i][j]` to store the minimum largest subarray sum for splitting the first `j` elements of `nums` into `i` subarrays.
- The goal is to compute `dp[k][n]`, where `n` is the length of the array.
- To avoid recomputing sums, pre-calculate a `prefixSum` array where `prefixSum[i]` is the sum of elements from `nums[0]` to `nums[i-1]`.
- The base case is for `i=1`: `dp[1][j] = prefixSum[j]`, as splitting `j` elements into one subarray results in the sum of those `j` elements.
- The transition to compute `dp[i][j]` involves trying all possible split points `p` (where `0 <= p < j`). The last subarray would be `nums[p...j-1]`, and the first `p` elements would have been split into `i-1` subarrays.
- The recurrence relation is: `dp[i][j] = min(dp[i][j], max(dp[i-1][p], prefixSum[j] - prefixSum[p]))` for all valid `p`.
- The final answer is `dp[k][n]`.

## Binary Search on the Answer
This highly efficient approach uses binary search on the answer. The key insight is that if we can split the array with a maximum subarray sum of `x`, we can also do it for any value greater than `x`. This monotonic property allows us to search for the smallest possible value of this maximum sum within a defined range. The range for the answer is from the largest single element in the array to the total sum of the array.
**Time:** O(n * log(S)), where `n` is the length of the array and `S` is the sum of its elements. The binary search performs `O(log(S))` iterations, and each involves a linear `O(n)` scan of the array. · **Space:** O(1), as we only use a few variables to manage the binary search and the feasibility check.
**Pros:** Extremely efficient with a time complexity of `O(n * log(S))`.; Uses constant extra space, making it very memory-efficient.; It's a powerful and common technique for solving 'minimax' or 'maximin' type problems.
**Cons:** The approach can be less intuitive to discover compared to a direct DP solution.; It relies on correctly identifying the monotonic property of the problem.
### Explanation
This approach reframes the problem from finding the value to verifying if a given value is possible. The possible values for the minimized largest sum are bounded. The lower bound is the largest element in the array (as it must belong to some subarray), and the upper bound is the sum of all elements (the case for `k=1`).

We can binary search within this range `[max(nums), sum(nums)]`. For each `mid` value we test, we need to determine if it's possible to split the array into `k` or fewer subarrays such that no subarray's sum exceeds `mid`. This check can be done greedily in linear time.

We iterate through the array, accumulating a `currentSum`. As soon as adding the next element would make `currentSum` exceed `mid`, we must start a new subarray. We count the total number of subarrays required. If this count is less than or equal to `k`, then `mid` is a feasible largest sum, and we try to find an even smaller one by narrowing our search to the lower half. Otherwise, `mid` is too small, and we must search in the upper half.

```java
class Solution {
    public int splitArray(int[] nums, int k) {
        long low = 0;
        long high = 0;
        for (int num : nums) {
            low = Math.max(low, num);
            high += num;
        }

        long ans = high;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (isFeasible(nums, k, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return (int) ans;
    }

    // Checks if we can split nums into k or fewer subarrays,
    // with each subarray's sum not exceeding maxSum.
    private boolean isFeasible(int[] nums, int k, long maxSum) {
        int subarraysNeeded = 1;
        long currentSum = 0;
        for (int num : nums) {
            if (currentSum + num > maxSum) {
                subarraysNeeded++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }
        return subarraysNeeded <= k;
    }
}
```
### Algorithm
- The answer must lie in the range `[max(nums), sum(nums)]`.
- We can binary search for the minimum possible value `x` in this range that can be the largest subarray sum.
- For a given `x`, we need a helper function `isFeasible(x)` to check if it's possible to split `nums` into `k` or fewer subarrays, each with a sum at most `x`.
- The `isFeasible(x)` function can be implemented greedily: iterate through `nums`, creating subarrays. Start a new subarray whenever the current one's sum would exceed `x`.
- Count the number of subarrays needed. If this count is `_<= k`, then `x` is a feasible maximum sum.
- In the binary search, if `isFeasible(mid)` is true, it means `mid` is a possible answer, so we try for a smaller one: `high = mid - 1`.
- If `isFeasible(mid)` is false, `mid` is too small, so we need to allow a larger sum: `low = mid + 1`.
- The smallest `mid` for which `isFeasible(mid)` is true is our answer.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} k * @return {number} */ var splitArray = function ( nums , k ) { let l = Math . max (... nums ); let r = nums . reduce (( a , b ) => a + b ); const check = mx => { let [ s , cnt ] = [ 0 , 0 ]; for ( const x of nums ) { s += x ; if ( s > mx ) { s = x ; if ( ++ cnt === k ) return false ; } } return true ; }; while ( l < r ) { const mid = ( l + r ) >> 1 ; if ( check ( mid )) { r = mid ; } else { l = mid + 1 ; } } return l ; };
```

### CPP

```cpp
class Solution {
public:
  int splitArray(vector<int> &nums, int k) {
    int left = 0, right = 0;
    for (int &x : nums) {
      left = max(left, x);
      right += x;
    }
    auto check = [&](int mx) {
      int s = 1 << 30, cnt = 0;
      for (int &x : nums) {
        s += x;
        if (s > mx) {
          s = x;
          ++cnt;
        }
      }
      return cnt <= k;
    };
    while (left < right) {
      int mid = (left + right) >> 1;
      if (check(mid)) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
};

```

### Python

```python
class Solution:
    def splitArray(self, nums: List[int], k: int) -> int: def check(mx): s, cnt = inf, 0 for x in nums: s += x if s > mx: s = x cnt += 1 return cnt <= k left, right = max(nums), sum(nums) return left + bisect_left(range(left, right + 1), True, key=check)

```