# Maximum sub array problem – Kadane’s Algorithm

Given a sequence of n real numbers A(1) … A(n), program to find a contiguous subarray with the largest sum

For example,

var arr = new int[] {-2, 1,-3, 4,-1, 2, 1,-5, 4 };

the contiguous sub array with the largest sum is [4, −1, 2, 1], with sum 6.

### Solution

Solution via iterating over all array elements repeatedly, try each key elements

``````using System;
namespace MaximumSubarray
{
class Program
{
static void Main()
{
Console.WriteLine("Enter array size:");
var arr = new int[n]; //{ -2, 1, -3, 4, -1, 2, 1, -5, 4 };
Console.WriteLine("Enter array elements:");
for (var i = 0; i < n; i++)
{
}
Console.WriteLine(\$"Max sum of array is {MaxSum(arr)}");
}
static int MaxSum(int[] a)
{
var maxSum = 0;
for (var i = 0; i < a.Length; i++)
{
var newSum = 0;
for (var j = i; j < a.Length; j++)
{
newSum += a[j];
if (newSum > maxSum)
{
maxSum = newSum;
}
}
}
return maxSum;
}
}

}``````

#### Execute above program to see the output

Using Kadane’s algorithm – Dynamic Programming

Kadane’s algorithm scans the given array A[1…n] from left to right. In the jth step, it computes the subarray with the largest sum ending at j; this sum is maintained in variable current_sum]. Moreover, it computes the subarray with the largest sum anywhere in A[1…j] maintained in variable best_sum and easily obtained as the maximum of all values of current_sum seen so far, cf. line 7 of the algorithm.

Pseudocode:

``````def max_subarray(numbers):
"""Find the largest sum of any contiguous subarray."""
best_sum = 0
# or: float('-inf')
current_sum = 0
for x in numbers:
current_sum = max(0, current_sum + x)
best_sum = max(best_sum, current_sum)
return best_sum``````

Here is the C# solution of the problem using Kadane’s algorithm

``````using System;
namespace MaximumSubarray
{
class DynamicProgramming
{
static void Main()
{
Console.WriteLine("Enter array size:");
var arr = new int[n]; //{ -2, 1, -3, 4, -1, 2, 1, -5, 4 };
Console.WriteLine("Enter array elements:");
for (var i = 0; i < n; i++)
{
}
Console.WriteLine(\$"Max sum of array is {MaxSum(arr)}");
}

static int MaxSum(int[] a)
{
var maxSum = 0;
var newSum = 0;
foreach (var t in a)
{
newSum = Math.Max(t, newSum + t);
maxSum = Math.Max(maxSum, newSum);
}
return maxSum;
}
}
}``````