CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 12 of 12
  1. #1
    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. #2
    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?
    Debugging is twice as hard as writing the code in the first place.
    Therefore, if you write the code as cleverly as possible, you are, by
    definition, not smart enough to debug it.
    - Brian W. Kernighan

    To enhance your chance's of getting an answer be sure to read
    http://www.codeguru.com/forum/announ...nouncementid=6
    and http://www.codeguru.com/forum/showthread.php?t=366302 before posting

    Refresh your memory on formatting tags here
    http://www.codeguru.com/forum/misc.php?do=bbcode

    Get your free MS compiler here
    https://visualstudio.microsoft.com/vs

  3. #3
    Join Date
    Mar 2012
    Posts
    19

    Re: Maximum of two consecutive elements

    Quote Originally Posted by S_M_A View Post
    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. #4
    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?
    Debugging is twice as hard as writing the code in the first place.
    Therefore, if you write the code as cleverly as possible, you are, by
    definition, not smart enough to debug it.
    - Brian W. Kernighan

    To enhance your chance's of getting an answer be sure to read
    http://www.codeguru.com/forum/announ...nouncementid=6
    and http://www.codeguru.com/forum/showthread.php?t=366302 before posting

    Refresh your memory on formatting tags here
    http://www.codeguru.com/forum/misc.php?do=bbcode

    Get your free MS compiler here
    https://visualstudio.microsoft.com/vs

  5. #5
    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. #6
    Join Date
    Oct 2006
    Location
    Sweden
    Posts
    3,654

    Re: Maximum of two consecutive elements

    Debugging is twice as hard as writing the code in the first place.
    Therefore, if you write the code as cleverly as possible, you are, by
    definition, not smart enough to debug it.
    - Brian W. Kernighan

    To enhance your chance's of getting an answer be sure to read
    http://www.codeguru.com/forum/announ...nouncementid=6
    and http://www.codeguru.com/forum/showthread.php?t=366302 before posting

    Refresh your memory on formatting tags here
    http://www.codeguru.com/forum/misc.php?do=bbcode

    Get your free MS compiler here
    https://visualstudio.microsoft.com/vs

  7. #7
    Join Date
    Mar 2012
    Posts
    19

    Re: Maximum of two consecutive elements

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

  8. #8
    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?
    Debugging is twice as hard as writing the code in the first place.
    Therefore, if you write the code as cleverly as possible, you are, by
    definition, not smart enough to debug it.
    - Brian W. Kernighan

    To enhance your chance's of getting an answer be sure to read
    http://www.codeguru.com/forum/announ...nouncementid=6
    and http://www.codeguru.com/forum/showthread.php?t=366302 before posting

    Refresh your memory on formatting tags here
    http://www.codeguru.com/forum/misc.php?do=bbcode

    Get your free MS compiler here
    https://visualstudio.microsoft.com/vs

  9. #9
    Join Date
    May 2009
    Posts
    2,413

    Re: Maximum of two consecutive elements

    Quote Originally Posted by irpersian20 View Post
    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. #10
    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. #11
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Maximum of two consecutive elements

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  12. #12
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    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
  •  





Click Here to Expand Forum to Full Width

Featured