# recursive algorithm to find the max sum of 2 numbers

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.

• Why does it need to be recursive? Commented Dec 19, 2016 at 14:31

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.

• thnank u but where is the recursive? Commented Dec 17, 2016 at 8:05
• Could you explain or show the recursive part?
– Evil
Commented Dec 19, 2016 at 17:17
• Please consider not to encourage undesirable posting behaviour. Commented Dec 19, 2016 at 18:39
• @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? Commented Dec 21, 2016 at 0:00