Solved

Finding maximum sum of contigious elements.

Posted on 2015-01-03
2
122 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 69

Accepted Solution

by:
Qlemo earned 250 total points
ID: 40530125
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
ID: 40530458
When all negative, the maximum sum would contain 0 contigious elements, and the algorithm will correctly produce maxsofar=0
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

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…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

756 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