-2
$\begingroup$

I am looking for a recursive algorithm to find the max sum of 2 numbers in an array, and the numbers can't be "neighbours" ( for example $a[0]$ and $a[1]$ or $a[4]$ and $a[5]$, in general $a[i]$ and $a[i+1]$ )

example: for the array 5 8 3 9 20 1 4, the result will be 28.

Improve this question
$\endgroup$
1
  • $\begingroup$ Why does it need to be recursive? $\endgroup$
    – paparazzo
    Dec 19, 2016 at 14:31

1 Answer 1

Reset to default
5
$\begingroup$

Pick the four largest numbers in the array, $X \geq Y \geq Z \geq U$, and check for a few cases.

If $X$, $Y$ are not neighbours $\implies$ largest sum is $X + Y$.

Otherwise if $X$, $Z$ are not neighbours $\implies$ largest sum is $X + Z$.

Otherwise ($X$ is between $Y$ and $Z$) $\implies$ largest sum is $\max(Y + Z, X + U)$.

How did I get the solution: Well, the restriction is very mild, so it seemed likely that the largest sum would be found by adding two of the largest numbers. I tried with the three largest numbers, and found that $Y + Z$ could be small compared to $X$ plus the next smaller number, so the largest 4 were needed.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ thnank u but where is the recursive? $\endgroup$
    – Ginger
    Dec 17, 2016 at 8:05
  • $\begingroup$ Could you explain or show the recursive part? $\endgroup$
    – Evil
    Dec 19, 2016 at 17:17
  • $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$
    – Raphael ♦
    Dec 19, 2016 at 18:39
  • 1
    $\begingroup$ @Ginger: It solves the problem. So who cares if it isn't recursive? It's not homework, right? Is there a reason why you think a recursive solution would be better? $\endgroup$
    – gnasher729
    Dec 21, 2016 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.