# Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6

```    // C# program to print largest contiguous array sum
class Program
{
static int maxSubArraySum(int[] a)
{
int size = a.Length;
int max_so_far = int.MinValue,
max_ending_here = 0;

for (int i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];

if (max_so_far < max_ending_here)
max_so_far = max_ending_here;

if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}

public static void Main()
{
int[] a = { -2,1,-3,4,-1,2,1,-5,4 };
Console.Write("Maximum contiguous sum is " + maxSubArraySum(a));
}
}
```

Output:

Dry run:

• i=0 and it’s value is -2
max_ending_here=0+(-2)
max_so_far=0 because max_ending_here is less than max_so_far
max_ending_here = 0 because max_ending_here is less than 0
• i=1 and it’s value is 1
max_ending_here=0+(1)
max_so_far=1 because max_ending_here is greater than max_so_far
max_ending_here = 1
• i=2 and it’s value is -3
max_ending_here=1+(-3)
max_so_far=1 because max_ending_here is less than max_so_far
max_ending_here = 0  because max_ending_here is less than 0
• i=3 and it’s value is 4
max_ending_here=0+(4)
max_so_far=4 because max_ending_here is greater than max_so_far
max_ending_here = 4
• i=4 and it’s value is -1
max_ending_here=4+(-1)
max_so_far=4 because max_ending_here is less than max_so_far
max_ending_here = 3
• i=5 and it’s value is 2
max_ending_here=3+(2)
max_so_far=5 because max_ending_here is greater than max_so_far
max_ending_here = 5
• i=6 and it’s value is 1
max_ending_here=5+(1)
max_so_far=6 because max_ending_here is greater than max_so_far
max_ending_here = 6
• i=7 and it’s value is -5
max_ending_here=6+(-5)
max_so_far=6 because max_ending_here is less than max_so_far
max_ending_here = 1
• i=8 and it’s value is 4
max_ending_here=1+(4)
max_so_far=6 because max_ending_here is less than max_so_far
max_ending_here = 5