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.