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

Groups > comp.programming > #2910

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

Show all headers | View raw

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

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