Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 155
  • Last Modified:

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

0
Nusrat Nuriyev
Asked:
Nusrat Nuriyev
2 Solutions
 
QlemoC++ 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
 
ozoCommented:
When all negative, the maximum sum would contain 0 contigious elements, and the algorithm will correctly produce maxsofar=0
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now