maxSubarray

https://leetcode.com/problems/maximum-subarray/

class Solution:
    def maxSubArray(self, A: List[int]) -> int:
        dp = A[:]
        for i in range(1, len(A)):
            dp[i] = (dp[i-1] if dp[i-1]>0 else 0) + A[i]
        return max(dp)

https://leetcode.com/contest/weekly-contest-105/problems/maximum-sum-circular-subarray/

Reference of this figure [1]

Proof of case 2

max(prefix+suffix) = max(total sum — subarray) = total sum + max(-subarray) = total sum — min(subarray) [2]

class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        max_dp, min_dp = A[:], A[:]
        for i in range(1, len(A)):
            max_dp[i] = (max_dp[i-1] if max_dp[i-1]>0 else 0) + A[i]
            min_dp[i] = (min_dp[i-1] if min_dp[i-1]<0 else 0) + A[i]
        max_, min_ = max(max_dp), min(min_dp)
        S = sum(A)
        return max(max_, S-min_) if S!=min_ else max_

Reference

[1] https://leetcode.com/problems/maximum-sum-circular-subarray/discuss/178422/One-Pass/183810

[2]https://leetcode.com/problems/maximum-sum-circular-subarray/discuss/178422/One-Pass/195770