Find the minimum sum contiguous subarray
public class MinSumContiguousSubarray {
public static void main(String[] args) {
int[] arr = {3, -4, 2, -3, -1, 7, -5};
int[] minSubarray = findMinSumContiguousSubarray(arr);
System.out.print("Minimum sum contiguous subarray: ");
for (int i = 0; i < minSubarray.length; i++) {
System.out.print(minSubarray[i] + " ");
}
}
public static int[] findMinSumContiguousSubarray(int[] arr) {
int n = arr.length;
int currentSum = 0;
int minSum = Integer.MAX_VALUE;
int startIndex = 0, endIndex = 0, s = 0;
for (int i = 0; i < n; i++) {
currentSum += arr[i];
if (currentSum < minSum) {
minSum = currentSum;
startIndex = s;
endIndex = i;
}
if (currentSum > 0) {
currentSum = 0;
s = i + 1;
}
}
int[] subarray = new int[endIndex - startIndex + 1];
for (int i = 0; i < subarray.length; i++) {
subarray[i] = arr[startIndex + i];
}
return subarray;
}
}
In this code, we declare an array arr
with some sample values, and call the findMinSumContiguousSubarray
function to find the subarray with the minimum sum. The function takes the input array as its parameter and returns the minimum sum contiguous subarray as an array.
Inside the findMinSumContiguousSubarray
function, we initialize some variables: currentSum
, minSum
, startIndex
, endIndex
, and s
. The currentSum
variable keeps track of the sum of the current subarray, the minSum
variable keeps track of the minimum sum found so far, the startIndex
and endIndex
variables keep track of the indices of the subarray with the minimum sum, and the s
variable keeps track of the starting index of the current subarray.
We then iterate through the input array using a for
loop, and add each element to currentSum
. If currentSum
becomes less than minSum
, we update minSum
, startIndex
, and endIndex
. We also check if currentSum
is greater than zero, and if so, we reset currentSum
to zero and update s
to the current index plus one.
At the end of the loop, we create a new array to store the minimum sum contiguous subarray, and copy the elements of the subarray from the input array to the new array using the startIndex
and endIndex
variables.
The time complexity of this algorithm is O(n), since we are iterating through the input array only once.