Smallest sum contiguous subarray

Problem statement

Given an array arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the minimum sum and return its sum.

link to the problem could be found here, https://practice.geeksforgeeks.org/problems/smallest-sum-contiguous-subarray/1

Sample Input and Outputs

Example 1

Input: 
    arr[] = {3,-4, 2,-3,-1, 7,-5}
Output: -6

Explanation: 
sub-array which has smallest 
sum among all the sub-array is {-4,2,-3,-1} = -6

Example 2

Input:
    arr[] = {2, 6, 8, 1, 4}
Output: 1
Explanation: 
sub-array which has smallest
sum among all the sub-array is {1} = 1

Expected Time Complexity: O(N)

Expected Auxiliary Space: O(1)

Solution

Here the most simplest and efficient solution is based upon the Kadane’s Algorithm. Which sweeps the iterator (here mentioned as current sum) from element to element, meanwhile after every updated value of the iterator, or current sum, this value is being checked with minimum result sum, if minimum sum get a further minimum value, then the contents are updated, else not.

Meanwhile if the current sum any where exceeds the 0, then we need to reset the current sum to zero. This means for any value here on it would make sense to ignore the subarray till this point, as if considered would result into few positive numbers, that inturn would oppose the interest of the problem to find minimum number (to which only negative numbers contribute). So avoid taking positive numbers into current sum.

class Solution
{
    static int smallestSumSubarray(int a[], int size) {
        int minSum = Integer.MAX_VALUE;
        int curSum = 0;
        for(int i : a) {
            curSum += i;
            minSum = Math.min(minSum, curSum);
            curSum = Math.min(curSum, 0);
        }
        return minSum;
    }
}