题解 | #牛群的最大能量环#

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 计算不包括末尾元素的子数组的最大子数组和（用 max_sum 记录）；
2. 计算包括末尾元素的子数组的最大子数组和（用 cur_sum 记录）；
3. 计算不包括头元素的子数组的最小子数组和（用 min_sum 记录，这里使用了负数）；
4. 如果最大子数组和 max_sum 小于 0，则说明所有元素都是负数，直接返回 max_sum；
5. 否则，最终的答案就是 max(max_sum, cur_sum - min_sum)。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param energy int整型一维数组
# @return int整型
#
class Solution:
    def maxEnergyCircular(self, energy: List[int]) -> int:
        n = len(energy)
        dp = [0] * n
        max_sum = energy[0]
        cur_sum = energy[0]
        for i in range(1, n):
            dp[i] = max(dp[i-1], 0) + energy[i]
            max_sum = max(max_sum, dp[i])
            cur_sum += energy[i]
        min_sum = energy[0]
        for i in range(1, n):
            dp[i] = min(dp[i-1], 0) + energy[i]
            min_sum = min(min_sum, dp[i])
        return max_sum if max_sum < 0 else max(max_sum, cur_sum - min_sum)