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
Printable View
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
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:Quote:
Originally Posted by S_M_A
3,7,1,6,9,2,3
6+9=15
Maximum of two elements together
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?
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
Ok, so this is an assignment? http://forums.codeguru.com/showthread.php?t=366302
Dear my friendQuote:
Originally Posted by S_M_A
It's not my homework.
Sample test questions , could not find an appropriate solution
But it's still you that should do the code isn't it?
You just use the usual recursive divide and conquer algorithm.Quote:
Originally Posted by irpersian20
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.
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.
That approach may give an incorrect answer as the two largest numbers might not be adjacent in the original list.Quote:
Originally Posted by ninja9578
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.