deepak tripathi
BAN USERusing System;
namespace Algorithms
{
class Program
{
static void Main(string[] args)
{
Program p = new Program();
int[] array = { 31, -41, 59, 26, -53, 58, 97, -93, -23, 84 };
int result = p.ArrayMaxSum(0, array.Length - 1, array);
Console.Write(result.ToString());
Console.ReadKey();
}
public int ArrayMaxSum(int lowerBound, int upperBound, int[] array)
{
if (lowerBound > upperBound)
return 0;
if ( lowerBound == upperBound )
{
return Math.Max(0,array[lowerBound]);
}
int mid = (lowerBound + upperBound) / 2;
int sum = 0;
int lmax = 0;
for (int i = mid; i >= lowerBound; i--)
{
sum = sum + array[i];
lmax = Math.Max(lmax, sum);
}
sum = 0;
int rmax = 0 ;
for (int i = mid+1 ; i <= upperBound; i++)
{
sum = sum + array[i];
rmax = Math.Max(rmax, sum);
}
return Math.Max((lmax + rmax), Math.Max(ArrayMaxSum(lowerBound, mid, array), ArrayMaxSum(mid + 1, upperBound, array)));
}
}
}
complexity is O ( n log n )
- deepak tripathi April 24, 2013