Challenge problem 2As 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
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. |