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

Groups > comp.programming > #2909

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

Show all headers | View raw

Robert Wessel writes:
> On 25 Jan 2013 11:01:56 +0200, Jussi Piitulainen wrote:
> 
> >Robert Wessel writes:
> >> On Thu, 24 Jan 2013 18:28:47 -0800 (PST), billmann
> >> >On Thursday, January 24, 2013 8:07:46 PM UTC-5,
> >> > robert...@yahoo.com wrote:
> >> >> On Thu, 24 Jan 2013 16:24:25 -0800 (PST), billmann
> >> >> > Does anyone know an algorithm (that uses recursion only! No
> >> >> > Loops) that can find the maximum sum of elements in an array
> >> >> > with the constraint that you cannot choose items that are
> >> >> > adjacent to one another. The function I am trying to write can
> >> >> > only take in an Integer Array but we are allowed to write
> >> >> > helper functions either outside or inside the main function
> >> >> > that can take in anything you want.
> >[snip]
> >> A dozen lines, for me.  28 lines total including seven blank lines,
> >> and a minimal test driver.  Could be less if you use a more compact
> >> brace style than I do.
> >
> >What do you do if the array is all negative numbers? I interpreted it
> >so that I can omit all of them and return 0, the empty sum. For me,
> >this is the obvious interpretation, but I know there are different
> >people out there.
> >
> >(Half a dozen straightforward Scheme lines, a half-a-dozen-line
> >comment to convince me that the reasoning is correct. Test in REPL.)
> 
> I did mine in C, and zero for an all-negative set of inputs is the
> only reasonable interpretation I can see - the OP's spec did not
> specify a minimum number of terms to sum.  I don't have any special
> handling for negative numbers, but obviously a trial sum including a
> negative term is never going to be the answer.

Thanks.

I have three branches: no elements, one element, more than one. A
singleton of a negative number would have produced a negative number
if I hadn't handled it specially. Perhaps your version is nicer.

> I'm doing a fairly straightforward exhaustive depth first search on
> the selection space, and several possible optimizations come to
> mind, but all involving considerably more complexity (at least
> relative to the current approach).  The simple approach is
> approximately O(2**n), but you can decompose the problem into
> computing the maximum sums of several combinations of left and right
> haves, including and not including the element next to the division,
> and then combining them in the three valid combinations.  That can
> be done recursively, of course, and I think, would reduce this to an
> O(n*log(n)) problem.

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.

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