text
function bruteForce(index, subarraysLeft):
    if subarraysLeft == 1:
        return sum(nums[index...end])
    
    minLargestSum = infinity
    currentSum = 0
    
    for i from index to n - subarraysLeft:
        currentSum += nums[i]
        remainingMax = bruteForce(i + 1, subarraysLeft - 1)
        currentMax = max(currentSum, remainingMax)
        minLargestSum = min(minLargestSum, currentMax)
        
    return minLargestSum

Complexity Analysis: The time complexity is roughly proportional to the number of combinations of choosing k-1 split points among N-1 positions, which is $\binom{N-1}{k-1}$. In the worst case, this is exponential. Given the constraint $N \le 1000$, an exponential solution will result in a Time Limit Exceeded (TLE) error.

Core Insight for Split Array Largest Sum

The core insight is to invert the problem. Instead of asking "What is the minimized largest sum?", we ask: "Given a candidate maximum sum S, can we split the array into k or fewer subarrays such that no subarray sum exceeds S?"

This boolean question—let's call it canSplit(S)—is much easier to solve. We can determine canSplit(S) using a greedy approach in linear time.

Because the property is monotonic, we can binary search for the smallest S where canSplit(S) returns true.

1. Lower Bound (left): The smallest possible value for the largest sum is the maximum single element in nums. We cannot have a subarray sum smaller than the largest element itself.
2. Upper Bound (right): The largest possible value is the sum of all elements in nums (the case where $k=1$).

Visual Description: Imagine a number line representing all possible values for the "largest sum".

• On the left side (small values), the capacity is too tight; we would need more than k subarrays to fit all numbers. The condition fails.
• On the right side (large values), the capacity is generous; we can easily fit numbers into k (or fewer) subarrays. The condition passes.
• We are looking for the exact boundary where the condition switches from False to True. Binary search efficiently narrows this range by checking the midpoint and discarding the half that doesn't contain the boundary.

Execution Flow

Let's trace nums = [7, 2, 5, 10, 8] with k = 2.

1. Initialization:

   • left = 10 (max element).
   • right = 32 (sum of all elements).

2. Iteration 1:

   • mid = (10 + 32) / 2 = 21.
   • Check canSplit(21):
     • Subarray 1: [7, 2, 5] (Sum 14). Adding 10 exceeds 21. Split.
     • Subarray 2: [10, 8] (Sum 18).
     • Count = 2. Since $2 \le k$, canSplit returns True.
   • mid is valid. We try to find a smaller valid sum.
   • right becomes 20.

3. Iteration 2:

   • mid = (10 + 20) / 2 = 15.
   • Check canSplit(15):
     • Subarray 1: [7, 2, 5] (Sum 14). Adding 10 exceeds 15. Split.
     • Subarray 2: [10]. Adding 8 exceeds 15. Split.
     • Subarray 3: [8].
     • Count = 3. Since $3 > k$, canSplit returns False.
   • mid is too small.
   • left becomes 16.

4. Iteration 3:

   • mid = (16 + 20) / 2 = 18.
   • Check canSplit(18):
     • Subarray 1: [7, 2, 5] (Sum 14). Split.
     • Subarray 2: [10, 8] (Sum 18).
     • Count = 2. Valid.
   • right becomes 17.

5. Iteration 4:

   • mid = (16 + 17) / 2 = 16.
   • Check canSplit(16): Returns False (needs 3 subarrays).
   • left becomes 17.

6. Iteration 5:

   • mid = (17 + 17) / 2 = 17.
   • Check canSplit(17): Returns False (needs 3 subarrays).
   • left becomes 18.

7. Termination:

   • left (18) > right (17). Loop ends.
   • Return left = 18.

Proof of Correctness

The correctness relies on two properties:

1. Monotonicity: If a capacity C is valid, any capacity C' > C is also valid (we can always split less or have smaller sums). If C is invalid, any C' < C is also invalid. This justifies Binary Search.
2. Greedy Strategy: In canSplit, we delay starting a new subarray as long as possible. This ensures we use the minimum number of subarrays for a given capacity. If the minimum number of subarrays needed for capacity X is $\le k$, then X is a feasible solution (we can always arbitrarily split more to reach exactly k without increasing the max sum).

Therefore, the algorithm finds the minimal S such that the greedy decomposition results in $\le k$ subarrays.

Reference Implementation

C++ Solution for LeetCode 410

cpp
class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        long long left = 0;
        long long right = 0;
        
        // Initialize bounds
        for (int num : nums) {
            left = max(left, (long long)num);
            right += num;
        }
        
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            
            if (canSplit(nums, k, mid)) {
                // If feasible, try a smaller maximum sum
                right = mid - 1;
            } else {
                // If not feasible, we need a larger maximum sum
                left = mid + 1;
            }
        }
        
        return (int)left;
    }
    
private:
    bool canSplit(const vector<int>& nums, int k, long long maxLimit) {
        int subarrays = 1;
        long long currentSum = 0;
        
        for (int num : nums) {
            if (currentSum + num > maxLimit) {
                // Exceeds limit, must start new subarray
                subarrays++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }
        
        return subarrays <= k;
    }
};

Java Solution for LeetCode 410

java
class Solution {
    public int splitArray(int[] nums, int k) {
        long left = 0;
        long right = 0;
        
        // Initialize bounds
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            
            if (canSplit(nums, k, mid)) {
                // Try to minimize the largest sum
                right = mid - 1;
            } else {
                // Capacity too small, increase it
                left = mid + 1;
            }
        }
        
        return (int) left;
    }
    
    private boolean canSplit(int[] nums, int k, long maxLimit) {
        int subarrays = 1;
        long currentSum = 0;
        
        for (int num : nums) {
            if (currentSum + num > maxLimit) {
                subarrays++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }
        
        return subarrays <= k;
    }
}

Python Solution for LeetCode 410

python
class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def can_split(max_limit):
            subarrays = 1
            current_sum = 0
            
            for num in nums:
                if current_sum + num > max_limit:
                    subarrays += 1
                    current_sum = num
                else:
                    current_sum += num
            
            return subarrays <= k

        left = max(nums)
        right = sum(nums)
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if can_split(mid):
                # Try to find a smaller valid maximum sum
                right = mid - 1
            else:
                # Mid is too small, need larger capacity
                left = mid + 1
                
        return left

• Mistake: Setting left = 0 or left = min(nums).
• Reason: Every element must belong to some subarray. If the capacity is smaller than the largest single element, that element cannot fit anywhere.
• Consequence: The canSplit function logic breaks or requires extra complexity to handle "impossible to place" numbers.