BadNeighbors - Topcoder puzzle I'm learning Dynamic Programming, following the topcoder guide. I just solved the BadNeighbors puzzle. It passes all the test cases, but I don't have much experience, so I don't know if it's good.


  Puzzle Description:
  
  Each of the town's residents is willing to donate a certain amount, as specified in the int[] donations, which is listed in clockwise order around the well. However, nobody is willing to contribute to a fund to which his neighbor has also contributed. Next-door neighbors are always listed consecutively in donations, except that the first and last entries in donations are also for next-door neighbors. You must calculate and return the maximum amount of donations that can be collected.


def circle(lst):
    if len(lst) == 1:
        return lst[0]
    attempt_1 = _circle(lst, 0, len(lst)-1)
    attempt_2 = _circle(lst, 1, len(lst))
    return max(attempt_1, attempt_2)

def _circle(lst, start, end):
    prev, best = 0, 0
    for i in xrange(start, end):
        val = lst[i]
        current = val + best
        best = max(prev, best)
        prev = current
    return best


Edit: Check the comments of my selected answer for the full resolution.
Your code doesn't actually work for some tricky corner cases. Take e.g. [1, 10, 1, 1, 9]. It should be pretty obvious that 19 is the proper answer, but your code returns 11. To build a working solution, let's leave the circularity out, you have already figured how to get the result for a circular array running twice over a linear array.

As ususal with DP we will consider the array incrementally, and in an array dp[j] we will store the value of the maximum donation from the first j neighbors when the j-th neighbor is one of the donors. It is relatively straightforward to see that then:

dp[j+1] = max(dp[:j]) + lst[j+1]


Note that the max excludes the value over dp[j], as Python slices are right-exclusive.

We can turn this idea into code doing something like:

def mncs(lst):
    # MaximumNonContiguousSum
    dp = [0, 0]
    for item in lst:
        dp.append(max(dp[:-1]) + item)
    return max(dp)


This has a dreadful performance, \$O(n)\$ space and \$O(n^2)\$ time, because we are continuously rescanning the full dp array for the maximum. If we are only after the value of the maximum, and not the indices of the neighbors that produce it, we can minimize the overhead by keeping three numbers only, the previous maximum plus the last two entries:

def mncs(lst):
    dp = [0, 0, 0]
    for item in lst:
        m = max(dp[:-1])
        dp = [m, dp[-1], m + item]
    return max(dp)


Since we do constant work per entry, and keep a constant number of values as state, this solution uses \$O(1)\$ space and takes \$O(n)\$ time.

For completeness:

def mnccs(lst):
    # MaximumNonContiguousCircularSum
    return max(mncs(lst[1:]), mncs(lst[:-1]))