Finding maximum sum of contigious elements.

Could you confirm that linear algorithm is not so wide solution like O(n log n) - divide and conquer ?
Because I have noticed that ,when all negative, it does not work.
But, in John Bentley "Programming Pearls" book there is not mention about working correctly only with positive.

    int maxsofar = 0;
    int maxhere = 0;
    for (int j = 0; j < n; j++)
    {
        maxhere = mymax(maxhere + a[j], 0);
        maxsofar = mymax(maxsofar, maxhere);
    }

Open in new window

Nusrat NuriyevAsked:
Who is Participating?
 
QlemoConnect With a Mentor Batchelor and DeveloperCommented:
No, it does not work for only negative numbers. The first check is max(-something, 0), and that will always return 0. All values are lower than 0.
To have that work, you need to provide a largely negative number like -maxint instead of 0 in the max function.
0
 
ozoConnect With a Mentor Commented:
When all negative, the maximum sum would contain 0 contigious elements, and the algorithm will correctly produce maxsofar=0
0
All Courses

From novice to tech pro — start learning today.