1         public static int MaximumSubarray(int[] A)
 2         {
 3             int n = A.Length;
 4             int max = A[0], max_neg = A[0], sum = 0;
 5             bool flag = false; // for all the elements are negative integers
 6             for (int i = 0; i < n; i++)
 7             {
 8                 //if found one is not negative, toggle flag. And keep tracking the max negative number
 9                 if (A[i] >= 0)
10                     flag = true;
11                 else if (A[i] > max_neg)
12                     max_neg = A[i];
13 
14                 sum += A[i];
15                 if (sum < 0)
16                     sum = 0;
17                 else if (sum > max)
18                     max = sum;
19             }
20 
21             return flag ? max : max_neg;
22         }