Definition
- Minimum subarray sum asks for the smallest sum of any contiguous non-empty subarray.
- It is the mirror of Kadane's algorithm: replace
Math.maxwithMath.minthroughout. - At each position:
currentMin = Math.min(nums[i], currentMin + nums[i]). - Seed both
currentMinandglobalMinfrom the first element for all-positive arrays. - A clean alternative: negate all elements, run max Kadane, negate the result.
- Time is O(N) and space is O(1).
At the National Bank of India, Rajesh reviews a sequence of daily net cash movements for a treasury account, deposits as positives and withdrawals as negatives. He wants the worst continuous drawdown: the stretch of consecutive days that drained the most cash. He walks day by day, asking whether his running decline is still getting worse or whether he should start a fresh decline from today.
Understanding the Concepts
What is the Minimum Subarray Sum problem?
Given an array of integers that may include both positives and negatives, find the minimum sum obtainable from any contiguous non-empty subarray. This is the mirror image of the maximum subarray sum problem.
For example, given [3, -4, 2, -3, -1, 7, -5], the minimum subarray sum is -6, from the subarray [-4, 2, -3, -1].
How does the minimum Kadane variant work?
The same DP insight applies: the minimum subarray must end somewhere. If we compute the minimum sum of a subarray ending at each position, the overall answer is the smallest of those. We flip all comparisons from max to min.
package com.bank.service;
public class MinSubarraySumService {
/**
* Finds the worst continuous drawdown in a treasury account.
* Used by the National Bank of India liquidity-risk team.
*/
public static long minSubarraySum(long[] cashFlows) {
long currentMin = cashFlows[0];
long globalMin = cashFlows[0];
for (int i = 1; i < cashFlows.length; i++) {
currentMin = Math.min(cashFlows[i],
currentMin + cashFlows[i]);
globalMin = Math.min(globalMin, currentMin);
}
return globalMin;
}
public static void main(String[] args) {
long[] flows = {30000, -40000, 20000, -30000,
-10000, 70000, -50000};
System.out.println("Worst drawdown: Rs." + minSubarraySum(flows));
}
}
javac -d out com/bank/service/MinSubarraySumService.java
java -cp out com.bank.service.MinSubarraySumService
Worst drawdown: Rs.-60000
Why does the seeding matter for all-positive arrays?
If the array is all positive, the correct answer is the single smallest element. Seeding globalMin at zero would wrongly report zero, just as seeding globalMax at zero is wrong for the all-negative case in max Kadane.
// WRONG: seeds globalMin at 0
long globalMin = 0; // Returns 0 for [5, 3, 1] instead of 1
// CORRECT: seeds from first element
long globalMin = cashFlows[0]; // Returns 1 for [5, 3, 1]
How does the negate-and-reuse trick work?
A clean alternative is to negate every element, run standard maximum Kadane, and negate the result. This reuses one implementation for both the maximum and minimum problems.
package com.bank.service;
public class MinSubarrayViaNegation {
public static long minSubarraySum(long[] arr) {
long[] negated = new long[arr.length];
for (int i = 0; i < arr.length; i++) {
negated[i] = -arr[i];
}
return -maxSubarraySum(negated);
}
private static long maxSubarraySum(long[] arr) {
long cur = arr[0], best = arr[0];
for (int i = 1; i < arr.length; i++) {
cur = Math.max(arr[i], cur + arr[i]);
best = Math.max(best, cur);
}
return best;
}
}
How do you recover the drawdown indices?
The same tentative-start bookkeeping applies. Track a tentative start that resets on each restart, and commit the best start and end whenever the global minimum improves.
package com.bank.service;
public class MinSubarrayWithIndices {
public static void findWorstDrawdown(long[] flows) {
long curMin = flows[0], globalMin = flows[0];
int tempStart = 0, bestStart = 0, bestEnd = 0;
for (int i = 1; i < flows.length; i++) {
if (flows[i] < curMin + flows[i]) {
curMin = flows[i];
tempStart = i;
} else {
curMin = curMin + flows[i];
}
if (curMin < globalMin) {
globalMin = curMin;
bestStart = tempStart;
bestEnd = i;
}
}
System.out.println("Worst drawdown: day " + bestStart
+ " to day " + bestEnd + ", total: Rs." + globalMin);
}
public static void main(String[] args) {
long[] flows = {30000, -40000, 20000, -30000,
-10000, 70000, -50000};
findWorstDrawdown(flows);
}
}
Worst drawdown: day 1 to day 4, total: Rs.-60000
What are the edge cases?
Several edge cases require attention.
- All positive: the answer is the single smallest element.
- All negative: the answer is the sum of the entire array.
- Single element: the answer is that element.
- Large values: use
longfor financial data to prevent overflow.
package com.bank.core;
public class MinKadaneEdgeCases {
public static void main(String[] args) {
System.out.println(minSum(new long[]{5, 3, 1})); // 1
System.out.println(minSum(new long[]{-5, -3, -1})); // -9
System.out.println(minSum(new long[]{42})); // 42
}
static long minSum(long[] arr) {
long cur = arr[0], best = arr[0];
for (int i = 1; i < arr.length; i++) {
cur = Math.min(arr[i], cur + arr[i]);
best = Math.min(best, cur);
}
return best;
}
}
1
-9
42
What is the time and space complexity?
Time is O(N): a single pass. Space is O(1): two scalar variables. This is identical to the maximum variant.
What should a senior engineer know?
A senior engineer should understand these deeper aspects.
- Symmetry with max Kadane: minimum Kadane is not a separate algorithm. It is the same recurrence with the comparison direction flipped.
- The negate trick: negating and reusing max Kadane demonstrates structural understanding and reduces code duplication in production.
- Used in circular subarray: minimum Kadane is a component of the maximum circular subarray solution, where the wrapping case equals total minus minimum subarray sum.
- Drawdown analysis: in finance, the worst continuous drawdown is a key stress-testing metric.
Visual Overview
Cash Flows: [30, -40, 20, -30, -10, 70, -50] (thousands) ┌──────────────────────────────────────────────┐ │ i=0: cur=30, best=30 │ │ i=1: min(-40, 30-40)=-40, cur=-40, best=-40│ │ i=2: min(20, -40+20)=-20, cur=-20, best=-40│ │ i=3: min(-30, -20-30)=-50, cur=-50, best=-50│ │ i=4: min(-10, -50-10)=-60, cur=-60, best=-60│ │ i=5: min(70, -60+70)=10, cur=10, best=-60 │ │ i=6: min(-50, 10-50)=-40, cur=-40, best=-60│ └──────────────────────────────────────────────┘ Answer: -60 (subarray from index 1 to 4) Maximum vs Minimum Kadane: ┌────────────────────┐ ┌────────────────────┐ │ Max Kadane │ │ Min Kadane │ │ max(a[i], cur+a[i])│ │ min(a[i], cur+a[i])│ │ globalMax tracking │ │ globalMin tracking │ │ Seed from a[0] │ │ Seed from a[0] │ └────────────────────┘ └────────────────────┘
Key Takeaway
The minimum subarray sum problem asks for the smallest sum of any contiguous non-empty subarray, and you solve it with the mirror image of Kadane's algorithm in a single linear pass. The same DP insight applies: the minimum subarray ends somewhere, so you compute the minimum sum ending at each position and take the smallest. At each element, you either extend the running minimum or restart, choosing whichever is smaller.
The seeding pitfall mirrors the maximum variant. Seed both variables from the first element and iterate from the second, because the array might be all positive, in which case the correct answer is the single smallest element. The negate trick, running max Kadane on negated elements and negating the result, reuses one implementation for both problems and demonstrates structural understanding.
At the National Bank of India, Rajesh used this on the liquidity-risk team. Daily net cash movements for a treasury account arrived as signed amounts, and the team needed the worst continuous drawdown for stress-testing. The index-tracking extension identified the exact date range of the worst drawdown, which fed directly into the intraday liquidity buffer calculations.
The senior-level insight is recognizing that minimum Kadane is the same recurrence with a flipped comparison, not a separate algorithm. This symmetry means you can solve both variants with one function and a negation, which is the kind of structural understanding that impresses interviewers.
Remember one sentence: minimum Kadane is maximum Kadane with Math.max replaced by Math.min, seeded from the first element, finding the worst continuous drawdown.
---