Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #2914

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

Show all headers | View raw

Willem writes:

> That was my first approach.
> 
> na_sum(arr, left, right) {
>   if (right < left) return 0;
>   if (right == left) return arr[left];
>   mid = (left+right)/2;
>   return max(
>     na_sum(arr, left, mid-1) + na_sum(arr, mid+1, right),
>     na_sum(arr, leff, mid-2) + arr[mid] + na_sum(arr, mid+2, right)
>   );
> }

So, for a one-element array, you return the element, even if that is
negative. I think the answer should be 0 then. And for (-3, -1, 4) you
return max(-3 + 4, -1) = 1, no? I think the answer should be 4.

> > Yes, I did the exponential-time search: include or exclude the
> > first element in the sum with the appropriate maximum sum of the
> > rest. The two branches do _almost_ the same work but not quite.
> 
> If you do that, you're doing the same calculation over and over again.
> If you store the intermediate results, you get linear time:

Yes, mine is like the standard binary-branching Fibonacci function. I
think your na_sum above also needs to do repeat work, though the
halving in the middle, if it can be done correctly, should help. (I'm
not putting much thought into this. Just wondering, half asleep.)

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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