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

Groups > comp.programming > #2902 > unrolled thread

Maximum sum such that no two elements are adjacent.

Back to article view | Back to comp.programming

Contents

  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

#2902 — Maximum sum such that no two elements are adjacent.

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.  

[toc] | [next] | [standalone]

#2904

On Thu, 24 Jan 2013 16:24:25 -0800 (PST), billmann
<willmann817@gmail.com> wrote:

>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.  


It seems a straight-forward enough search function to write.  But we
don't do homework here.  Tell us what you've come up with so far.

[toc] | [prev] | [next] | [standalone]

#2905

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.  
> 
> 
> 
> 
> 
> It seems a straight-forward enough search function to write.  But we
> 
> don't do homework here.  Tell us what you've come up with so far.

I figured it out.  I got assistance from a classmate.  Thanks though. And its not that straightforward, recursion is a bitch sometimes.

[toc] | [prev] | [next] | [standalone]

#2906

On Thu, 24 Jan 2013 18:28:47 -0800 (PST), billmann
<willmann817@gmail.com> wrote:

>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.  
>> 
>> 
>> 
>> 
>> 
>> It seems a straight-forward enough search function to write.  But we
>> 
>> don't do homework here.  Tell us what you've come up with so far.
>
>I figured it out.  I got assistance from a classmate.  Thanks though. And its not
>that straightforward, recursion is a bitch sometimes.


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.

[toc] | [prev] | [next] | [standalone]

#2907

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.)

[toc] | [prev] | [next] | [standalone]

#2908

On 25 Jan 2013 11:01:56 +0200, Jussi Piitulainen
<jpiitula@ling.helsinki.fi> 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.

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.

[toc] | [prev] | [next] | [standalone]

#2909

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.

[toc] | [prev] | [next] | [standalone]

#2910

Jussi Piitulainen wrote:
) Robert Wessel writes:
)> 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.

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)
  );
}

) 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:

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;
}


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#2914

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.)

[toc] | [prev] | [next] | [standalone]

#2916

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.

:)

[toc] | [prev] | [next] | [standalone]

#2918

Robert Wessel <robertwessel2@yahoo.com> writes:

> On 25 Jan 2013 11:01:56 +0200, Jussi Piitulainen
> <jpiitula@ling.helsinki.fi> 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.   [...snip...]
>
> 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.

It is way better than exponential but not O( n * log(n) ).

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web