def circular_max_sum(self, A):
        n = len(A)
        left = [None for _ in A]
        right = [None for _ in A]

        cur, max_sum, idx = 0, A[0], 0
        for i in xrange(n):
            cur += A[i]
            if cur > max_sum:
                idx = i
                max_sum = cur
            left[i] = (max_sum, idx)

        cur, max_sum, idx = 0, A[n-1], n-1
        for i in xrange(n-1, -1, -1):
            cur += A[i]
            if cur > max_sum:
                idx = i
                max_sum = cur
            right[i] = (max_sum, idx)

        ret = Sum(A[0], 0, 0)
        for i in xrange(1, n):
            r = right[i]
            l = left[i-1]
            if ret.sum < r[0]+l[0]:
                ret = Sum(r[0]+l[0], r[1], l[1])

        return ret
dp:
dataset/ETHPy150Open algorhythms/LintCode/Continuous Subarray Sum II.py/Solution.circular_max_sum