Given an array of unordered positive and negative integers. Find the maximum sub array sum in the array.

For example the input array is :

 int [ ] arr  =  {2, -9, 5, 1, -4, 6, 0, -7, 8};


Output: Maximum sub array sum is 9.

Please check the following Algorithm for a better understanding :

In this case the output sub array starts from 5 (index : arr[2]) and ends in 9 (index : arr[8]). Check the following step by step calculation.

1. 5, 1, -4, 6, 0, -7, 8  → in this step we get (5 + 1) = 6

2.  6  , -4, 6, 0, -7, 8  → in this step we get (6 - 4) = 2

3.    2     , 6, 0, -7, 8  → in this step we get (2 + 6) = 8

4.          8  , 0 , -7, 8 → in this step we get (8 + 0) = 8

5.            8    , -7, 8 → in this step we get (8 -7) = 1

6.                1,      8 → in this step we get (1 + 8 ) = 9

 *  If all are negative numbers then keep track to minimum negative number. Because that will be our max sub array sum.

public class MaximumSubArraySum {

    public static int findMaximumSubArraySum(int[] input){
        int curSum = 0;
        int maxSum = 0;
        boolean isAllNegative = true;
        int minNegative = Integer.MIN_VALUE;
        
        for(int i = 0 ; i < input.length ; i++){
            // adding array elements one by one
            curSum += input[i];
            
            // replace currentSum with 0 when it becomes
            // less that 0
            if(curSum < 0){
                curSum = 0;
            }
            // replace maximum sum when current sum is greater
            // means we have a new subarray with greater sum
            if(maxSum < curSum){
                maxSum = curSum;
            }
            // making isAllNegative to false when ever we get a
            // positive number in the array
            if(input[i] > 0){
                isAllNegative = false;
            }
            // track the minimum negative number in the array
            // when all array numbers are negative
            if(input[i] < 0 && input[i] > minNegative && isAllNegative){
                minNegative = input[i];
            }
        }
        return isAllNegative ? minNegative :maxSum;
    }
    
    public static void main(String[] args) {
        int[] input = {2, -9, 5, 1, -4, 6, 0, -7, 8};
        System.out.println("Maximum subarray sum is " + findMaximumSubArraySum(input));
        
        int[] input1 = {1,5,-9,6,-3,4,-7};
        System.out.println("Maximum subarray sum is " + findMaximumSubArraySum(input1));
        
        int[] input2 = { -9,  -4,  -7};
        System.out.println("Maximum subarray sum is " + findMaximumSubArraySum(input2));
    }
}

Arrays 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself