gm
BAN USERpublic static void MaximumSumSubarray(int[] SourceArray)
{
int baseStart, baseEnd, baseSum;
int localStart, localEnd, localSum;
localStart = localEnd = localSum = 0;
baseStart = baseEnd = baseSum = 0;
Console.WriteLine("Source Array: ");
for (int i = 0; i < SourceArray.Length; i++)
{
Console.WriteLine("{0}: {1}", i, SourceArray[i]);
if (SourceArray[i] > 0 && localStart == 0)
{
localStart = i;
localSum = SourceArray[i];
}
else
{
localSum += SourceArray[i];
}
if ((i == SourceArray.Length - 1) || (SourceArray[i + 1] < 0 && localStart != 0))
{
localEnd = i;
if (localSum > baseSum)
{
baseSum = localSum;
baseStart = localStart;
baseEnd = localEnd;
}
localStart = localEnd = localSum = 0;
}
}
Console.WriteLine("Maximum sum subarray: Start:{0} End:{1} Sum:{2}", baseStart, baseEnd, baseSum);
Console.ReadLine();
}
Repjaydkelvey, Accountant at Apkudo
I am 34 years old and live in Houston with my family. I am working as a Human resources consultant ...
Yes, its of O(n*Log(n))
- gm June 20, 2012