-
June 3rd, 2012, 10:42 PM
#1
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
-
June 4th, 2012, 11:53 AM
#2
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?
-
June 4th, 2012, 11:56 AM
#3
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
-
June 4th, 2012, 12:16 PM
#4
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?
-
June 4th, 2012, 12:33 PM
#5
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
-
June 4th, 2012, 12:54 PM
#6
Re: Maximum of two consecutive elements
-
June 4th, 2012, 01:06 PM
#7
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
-
June 4th, 2012, 01:34 PM
#8
Re: Maximum of two consecutive elements
But it's still you that should do the code isn't it?
-
June 4th, 2012, 07:22 PM
#9
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.
-
June 7th, 2012, 08:07 PM
#10
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.
-
June 7th, 2012, 11:12 PM
#11
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.
-
June 8th, 2012, 06:18 PM
#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.
Best Regards,
BioPhysEngr
http://blog.biophysengr.net
--
All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|