Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder2.hal-mli.net!feeder.erje.net!us.feeder.erje.net!news2.arglkargh.de!nuzba.szn.dk!pnx.dk!news.stack.nl!.POSTED!not-for-mail
From: Willem <willem@turtle.stack.nl>
Newsgroups: comp.programming
Subject: Re: Maximum sum such that no two elements are adjacent.
Date: Fri, 25 Jan 2013 15:02:49 +0000 (UTC)
Organization: Stack Usenet News Service
Lines: 62
Message-ID: <slrnkg57kp.1ve1.willem@turtle.stack.nl>
References: <0437fd09-e678-4867-aec7-31a11db955d6@googlegroups.com> <6gm3g8pqkj8ifd5s57prf04majr42h1eim@4ax.com> <fc6b5d4a-198a-422f-9aec-34756aa6a487@googlegroups.com> <el84g8hsjm8apkp5amh5g4r4lavh9rb36l@4ax.com> <qotk3r11vqz.fsf@ruuvi.it.helsinki.fi> <7mo4g8ha1hgkqboduvbs3gqgg5fbl95g8q@4ax.com> <qot1ud9ctgo.fsf@ruuvi.it.helsinki.fi>
NNTP-Posting-Host: turtle.stack.nl
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Trace: mud.stack.nl 1359126169 65859 2001:610:1108:5010::132 (25 Jan 2013 15:02:49 GMT)
X-Complaints-To: abuse@stack.nl
NNTP-Posting-Date: Fri, 25 Jan 2013 15:02:49 +0000 (UTC)
User-Agent: slrn/0.9.9p1 (FreeBSD)
Xref: csiph.com comp.programming: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