Split Array Largest Sum
Mahabharata — Drona's K-Division — Minimizing the Maximum Burden in Any Platoon
k खण्डों में विभाजन — अधिकतम खण्ड-योग न्यूनतम। एक ही सूत्र — तीन प्रश्नों का उत्तर॥
*Divide into k parts — minimize the maximum part sum. One formula — the answer to three questions.*
The Story
Split an array into k non-empty subarrays (in order) to minimize the largest subarray sum.
For `nums=[7,2,5,10,8]`, k=2: split [7,2,5] and [10,8] → max=18. Or [7,2,5,10] and [8] → max=24. Or [7] and [2,5,10,8] → max=25. Min max = 18. Answer=18.
**This is IDENTICAL to bs-17 (Book Allocation):** - Book Allocation: minimize max pages, m students - Split Array: minimize max subarray sum, k parts - Both: ordered array, minimize maximum partition sum
Same code, different variable names: ```java int lo=max(nums), hi=sum(nums); while (lo < hi) { int mid=(lo+hi)/2; int parts=1, current=0; for (int n : nums) { if (current+n > mid) { parts++; current=0; } current += n; } if (parts <= k) hi=mid; else lo=mid+1; } return lo; ```
Drona divided his army into k platoons. He wanted no platoon to carry more than necessary — minimizing the maximum load. The binary search found the optimal split in O(n log(sum)) time.
**The key insight of this entire problem family:** "Is it possible to achieve maximum partition sum ≤ mid using at most k parts?" is monotone in mid. Larger mid → easier (fewer parts needed). Binary search on this monotone condition.
The DP Approach
DP: dp[i][j] = min max sum splitting first i elements into j parts. O(n²k).
public int splitArrayDP(int[] nums, int k) {
int n = nums.length;
int[] prefix = new int[n+1];
for (int i=0;i<n;i++) prefix[i+1]=prefix[i]+nums[i];
int[][] dp = new int[n+1][k+1];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
dp[0][0] = 0;
for (int i=1;i<=n;i++)
for (int j=1;j<=k;j++)
for (int m=j-1;m<i;m++)
if (dp[m][j-1]!=Integer.MAX_VALUE)
dp[i][j]=Math.min(dp[i][j],Math.max(dp[m][j-1],prefix[i]-prefix[m]));
return dp[n][k];
}Drona's Minimize-Maximum Wisdom
public int splitArray(int[] nums, int k) {
int lo = 0, hi = 0;
for (int n : nums) { lo = Math.max(lo, n); hi += n; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int parts = 1, current = 0;
for (int n : nums) {
if (current + n > mid) { parts++; current = 0; }
current += n;
}
if (parts <= k) hi = mid;
else lo = mid + 1;
}
return lo;
}Step-by-Step Walkthrough
[1,2,3,4,5], k=3 lo=5,hi=15 mid=10: [1+2+3+4=10],[5]→2≤3→hi=10 mid=7: [1+2+3=6,+4>7→new],[4+5=9>7→new],[5]→3≤3→hi=7 mid=6: [1+2+3=6],[4+5=9>6→new],[5] wait: 4+5>6→[4],[5]→4 parts>3→lo=7 lo==hi=7→return 7 ✅
Deep Insight
**The big family recap:** | Problem | Minimize/Maximize | Variable | |---------|-------------------|----------| | Koko (bs-11) | Minimize | eating speed k | | Bouquets (bs-12) | Minimize | days | | Ship (bs-16) | Minimize | ship capacity | | Books (bs-17) | Minimize | max pages | | Split Array (bs-18) | Minimize | max sum | | Aggressive Cows (bs-13) | MAXIMIZE | min distance |
All share the same binary search skeleton. The only differences are: the search space, and the feasibility check function.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²k) | O(nk) | DP approach |
| Optimal | O(n log sum) | O(1) | Binary search + O(n) greedy check |
Pattern Recognition
✅ Minimize maximum subarray sum with k splits ✅ Identical to bs-17 (Book Allocation) ✅ Same binary search + greedy template ✅ DP alternative exists but binary search is simpler **LeetCode Trigger Phrases:** → "split array largest sum" → "minimum of the maximum subarray sum" → Ordered partition minimum maximum
Bhagavad Gita 4.7
यदा यदा हि धर्मस्य ग्लानिर्भवति भारत। अभ्युत्थानमधर्मस्य तदात्मानं सृजाम्यहम्॥
Whenever there is a decline of dharma and rise of unrighteousness, O Bharata, then I manifest Myself.
Connection: The split array problem seeks the minimum maximum — the fairest possible distribution of burden. When one part bears an excessive load (adharma), the algorithm searches for the split that restores balance. Like Krishna's manifestation to restore dharmic equilibrium, binary search continuously checks and adjusts the partition boundary until the maximum burden is minimized — dharmic balance achieved through precise division.