Challenge problem 2

As before, I will give you an array of integers. The integers can be positive or negative, but not zero. This array can be very long (say, 100,000 elements). You need to write a program that will return two indices, i and j, such that the sum of the elements in the array between index i and index j (inclusive) is as large as possible.

For example, if the array is
-1 2 3 4 -5 -9 8 -4 8 -1
then your program should print "6 8" because the sum of the elements between indices 6 and 8 is "8 + -4 + 8 = 12", which larger than the sum between any other two indices.

A brute force solution would try all possible pairs of indices i and j and compute the sum between them, keeping track of which pair gave the largest sum. If the length of the array is n, then there are n possible values for i and O(n) possible values for j, and it takes O(n) time to compute the sum between indices i and j, for a total of O(n3). There is a linear time solution.