CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

Thread: Maximum of two consecutive elements

1. Junior Member
Join Date
Mar 2012
Posts
19

Maximum of two consecutive elements

Hello,
What are your ideas to solve the following problem?

Divide and conquer method
Algorithm to find the two consecutive elements in an array of n elements is the sum of the maximum

2. Elite Member
Join Date
Oct 2006
Location
Sweden
Posts
3,654

Re: Maximum of two consecutive elements

I'm not sure I understand. Do you mean how to find for instance 3,4 and 2,5 in the array 3,7,1,3,4,6,2,5 since 7 is the maximum value?

3. Junior Member
Join Date
Mar 2012
Posts
19

Re: Maximum of two consecutive elements

Originally Posted by S_M_A
I'm not sure I understand. Do you mean how to find for instance 3,4 and 2,5 in the array 3,7,1,3,4,6,2,5 since 7 is the maximum value?
For example:
3,7,1,6,9,2,3

6+9=15
Maximum of two elements together

4. Elite Member
Join Date
Oct 2006
Location
Sweden
Posts
3,654

Re: Maximum of two consecutive elements

I can't see any other way than iterating over the array while adding each pair and remember the maximum and what pair that created it. What if two pairs add up to the same maximum?

5. Junior Member
Join Date
Mar 2012
Posts
19

Re: Maximum of two consecutive elements

Use the divide-and-conquer approach to write a recursive algorithm that finds the maximum sum of two consecutive elements in an array.

For example:
1)3,7,1,6,9,2,3

6+9=15
Maximum of two elements together

2)
10,4,9,3,0,2
10+4=14

6. Elite Member
Join Date
Oct 2006
Location
Sweden
Posts
3,654

Re: Maximum of two consecutive elements

7. Junior Member
Join Date
Mar 2012
Posts
19

Re: Maximum of two consecutive elements

Originally Posted by S_M_A
Dear my friend
It's not my homework.
Sample test questions , could not find an appropriate solution

8. Elite Member
Join Date
Oct 2006
Location
Sweden
Posts
3,654

Re: Maximum of two consecutive elements

But it's still you that should do the code isn't it?

9. Elite Member
Join Date
May 2009
Posts
2,413

Re: Maximum of two consecutive elements

Originally Posted by irpersian20
could not find an appropriate solution
You just use the usual recursive divide and conquer algorithm.

The array index range is successively halved until there's just one index in a range. You add the element at that index position with the neighbour element to the left (if it exists). Then when the recursion winds back you take the maximum of the left and right branches.

10. Senior Member
Join Date
Jan 2009
Posts
1,689

Re: Maximum of two consecutive elements

Well, two consecutive numbers that yield the largest sum must be the two largest numbers, there is no way any other combination would produce a larger sum. So I would personally sort the list and pop off the two largest. Maybe the sample question is trying to imply that you should use a quicksort, bubble sort, or radix sort, all of which are divide and conquer sorts.

11. Elite Member Power Poster
Join Date
Jan 2006
Location
Singapore
Posts
6,768

Re: Maximum of two consecutive elements

Originally Posted by ninja9578
Well, two consecutive numbers that yield the largest sum must be the two largest numbers, there is no way any other combination would produce a larger sum. So I would personally sort the list and pop off the two largest.
That approach may give an incorrect answer as the two largest numbers might not be adjacent in the original list.

12. Re: Maximum of two consecutive elements

The recursive solution is based on the fact that if you divide the list in half that the maximum sub-sum is either:

(a) in the left half
(b) in the right half
(c) in the middle (that is composed of the right-most element of the left half and the left-most element of the right half)

You can sequentially half the list, solve the problem for the left and right halves recursively and then check the middle condition as you ascend back up the recursive tree.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•