BadNeighbors - Topcoder puzzle

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