Re: Maximum sum such that no two elements are adjacent.

From	Jussi Piitulainen <jpiitula@ling.helsinki.fi>
Newsgroups	comp.programming
Subject	Re: Maximum sum such that no two elements are adjacent.
Date	2013-01-26 14:57 +0200
Organization	University of Helsinki
Message-ID	<qot622kdrv1.fsf@ruuvi.it.helsinki.fi> (permalink)
References	(3 earlier) <el84g8hsjm8apkp5amh5g4r4lavh9rb36l@4ax.com> <qotk3r11vqz.fsf@ruuvi.it.helsinki.fi> <7mo4g8ha1hgkqboduvbs3gqgg5fbl95g8q@4ax.com> <qot1ud9ctgo.fsf@ruuvi.it.helsinki.fi> <slrnkg57kp.1ve1.willem@turtle.stack.nl>

Show all headers | View raw

Willem writes:

> If you store the intermediate results, you get linear time:
> 
> na_sum(arr, len) {
>   c = p = 0;
>   for (i = 0; i < len; i++) {
>     n = max(arr[i]+p, c);
>     p = c;
>     c = n;
>   }
>   return p2;
> }

max(arr[i] + p, p, c), because arr[i] may be negative, and return p;
but I see what you mean. There was, however, a requirement to use
recursion.

Is this another problem that is designed to give recursion a bad name?
This problem fell flat.

I have now a linear-time Scheme solution. The same as your solution
above. Recursive only because iteration truly is a special case of
recursion. Shorter than my exponential recursion: five lines. And
arguably easier to understand.

:)

Thread

Maximum sum such that no two elements are adjacent. billmann <willmann817@gmail.com> - 2013-01-24 16:24 -0800
  Re: Maximum sum such that no two elements are adjacent. Robert Wessel <robertwessel2@yahoo.com> - 2013-01-24 19:07 -0600
    Re: Maximum sum such that no two elements are adjacent. billmann <willmann817@gmail.com> - 2013-01-24 18:28 -0800
      Re: Maximum sum such that no two elements are adjacent. Robert Wessel <robertwessel2@yahoo.com> - 2013-01-25 00:18 -0600
        Re: Maximum sum such that no two elements are adjacent. Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-01-25 11:01 +0200
          Re: Maximum sum such that no two elements are adjacent. Robert Wessel <robertwessel2@yahoo.com> - 2013-01-25 05:13 -0600
            Re: Maximum sum such that no two elements are adjacent. Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-01-25 14:55 +0200
              Re: Maximum sum such that no two elements are adjacent. Willem <willem@turtle.stack.nl> - 2013-01-25 15:02 +0000
                Re: Maximum sum such that no two elements are adjacent. Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-01-25 23:41 +0200
                Re: Maximum sum such that no two elements are adjacent. Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-01-26 14:57 +0200
            Re: Maximum sum such that no two elements are adjacent. Tim Rentsch <txr@alumni.caltech.edu> - 2013-01-26 08:56 -0800

csiph-web