Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Finding maximum sum of contigious elements.

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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

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…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

856 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