## 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