Solved

Finding maximum sum of contigious elements.

Posted on 2015-01-03
2
102 Views
Last Modified: 2015-01-14
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
Comment
Question by:Nusrat Nuriyev
2 Comments
 
LVL 68

Accepted Solution

by:
Qlemo earned 250 total points
Comment Utility
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
 
LVL 84

Assisted Solution

by:ozo
ozo earned 250 total points
Comment Utility
When all negative, the maximum sum would contain 0 contigious elements, and the algorithm will correctly produce maxsofar=0
0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

7 Experts available now in Live!

Get 1:1 Help Now