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

#include <algorithm>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param energy int整型vector
     * @return int整型
     */
    int maxEnergyCircular(vector<int>& energy) {
        // write code here
        int dp[energy.size()],mindp[energy.size()];
        dp[0]=energy[0];
        mindp[0]=energy[0];
        int maxsum = energy[0],minsum=energy[0];
        int sum=0;
        for (int i = 0; i < energy.size(); ++i) {
            dp[i]=max(dp[i-1]+energy[i],energy[i]);
            maxsum=max(maxsum,dp[i]);
            mindp[i]=min(mindp[i-1]+energy[i],energy[i]);
            minsum=min(mindp[i-1],minsum);
            sum+=energy[i];
        }
        int t=sum-minsum;
        return max(maxsum,t);
    }
};

最大子序列和如果在中间区域，那么就是找最大子序列和；最大子序列如果在末端和前端之和，这种情况不好找最大；但是可以找出数组的最小子序列和，然后用sum减最小子序列和就是最大子序列和。