Find Minimum Subarray Sum in Java
Problem
The minimum subarray sum is the smallest possible sum of any contiguous run of elements within the array — including the possibility that a single very negative element is the best (lowest) choice on its own.
Given an array of integers, find the smallest sum achievable by any contiguous subarray.
Java Program
public class MinSubarraySum {
public static void main(String[] args) {
int[] arr = {3, -4, 2, -3, -1, 7, -5};
int minSum = arr[0];
for (int i = 0; i < arr.length; i++) {
int sum = 0; // reset for each new starting index
for (int j = i; j < arr.length; j++) {
sum += arr[j]; // extend the subarray by one element
if (sum < minSum) minSum = sum;
}
}
System.out.println("Minimum subarray sum: " + minSum);
}
}Output
Core Logic
Computing the sum of every possible contiguous subarray directly, and keeping track of the smallest one seen, checks every candidate explicitly.
- 1The outer loop picks a starting index
ifor a candidate subarray. - 2The inner loop extends the subarray one element at a time, adding
arr[j]to a runningsum. - 3After each extension,
sumis compared againstminSum, updating it whenever a smaller total is found. - 4By the time both loops finish, every one of the array's contiguous subarrays has had its sum checked.
[3, -4, 2, -3, -1, 7, -5], the subarray [-4, 2, -3, -1] sums to -6, the smallest total found across every subarray tried.Key Point: This checks every O(n²) subarray explicitly — the same exhaustive idea used to find a maximum subarray sum, just tracking the smaller total instead of the larger one.
Why: Every possible subarray's sum is computed directly by extending the inner loop's running total, so the nested loops do O(n²) work with no extra memory.
Key Concepts
Approach 2: Running Minimum (Optimized)
public class MinSubarraySumOptimized {
public static void main(String[] args) {
int[] arr = {3, -4, 2, -3, -1, 7, -5};
int minEndingHere = arr[0];
int minSoFar = arr[0];
for (int i = 1; i < arr.length; i++) {
minEndingHere = Math.min(arr[i], minEndingHere + arr[i]); // extend, or restart from here
minSoFar = Math.min(minSoFar, minEndingHere); // smallest subarray ending anywhere so far
}
System.out.println("Minimum subarray sum: " + minSoFar);
}
}
Output
Core Logic
At each position, deciding whether extending the previous running subarray still gives a lower sum than starting fresh right there finds the minimum in a single pass, without ever checking a subarray twice.
- 1
minEndingHeretracks the smallest sum of a subarray that ends exactly at the current position. - 2
minEndingHere = Math.min(arr[i], minEndingHere + arr[i])decides, at each step, whether extending the previous subarray still beats starting over fromarr[i]alone. - 3
minSoFartracks the best (smallest)minEndingHereseen across the whole scan, updated after every step. - 4By the end of one pass,
minSoFarholds the answer — no nested loop was ever needed.
[3, -4, 2, -3, -1, 7, -5], minEndingHere resets to -4 once the leading 3 no longer helps, then keeps extending through 2, -3, -1 to reach -6, which becomes minSoFar.Key Point: This is the same running-decision idea behind Kadane's algorithm, mirrored for the smallest sum instead of the largest — extend the running subarray only while doing so keeps improving the answer.
Why: Each element is visited exactly once, deciding whether to extend the running subarray or start fresh from the current element — no nested loop and no extra memory beyond two running variables.