There is an array containing both +ve and -ve numbers. Can you write an algo/prog to find the subarray having the maximum sum ?
For eg :-
Consider
12, 32, -154, 50 , 60 , 888, -10000, 3
In this array, the subarray which has the maximum sum is 50,60,888.
My only solution is a brute force approach...Check out the comment for my ans.
3 comments:
// Max sum is initialised to the least possible value.
// the variable maxsum gives the maximum sum of the subarray.
maxsum = MINUS_INFINITY;
// This is the loop.
for i = 0 to n
{
sum = 0;
for j = i to n
{
sum += a[j]
if ( sum > maxsum )
{
1. i = start_point of subarray
2. j = ending point of the subarray
3. maxsum = sum;
}
}
}
There is a full chapter dedicated to this question in Jon Bentley's Programming Pearls. Do read that.
The other assumption required to solve this is that any negative sum is taken as zero.
Actually, Sudeepa, your solution is really not quite Brute Force. The real brute force solution does an O(n^3) solution by considering all possible sub-arrays, and summing over them each time. You have optimized the summing part by keeping a cumulative sum for the inner most loop.
A divide and conquer algorithm will do the job in O(n-logn), but the linear time algorithm presented in the book is in a different league altogether.
it would be interesting to read that chapter ..... Divide and Conquer sounds interesting
Post a Comment