Programming Riddle of the Day, 11 March 2008

In this challenge, given an array of integers, the goal is to efficiently find the start and end indices of the sub array that has the greatest value when all of its elements are summed together. Note that because some elements of the array may be negative, the problem is not solved by simply returning the start and end elements of the array.

Here are some samples of the the integer arrays {} and the expected output:

static void find_highest(int[] a, out int start, out int end, out int hightotal)
{
int sum = 0;
int total = 0;
start = 0;
end = 0;
hightotal = 0;


for (int i = 0; i < a.Length; i++)
{
sum = a[i];

for (int j = i + 1; j < a.Length; j++)
if ((sum + a[j]) > sum)
{
sum += a[j];
end = j;
}
else
j = a.Length;

if (sum > total)
{
total = sum;
start = i;
}
}

hightotal = total;
}




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

int start = 0;
int end = 0;
int hightotal = 0;

find_highest(a, out start, out end, out hightotal);