题解 | #环形数组连续最大和#

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int []num=new int[n];
        for(int i=0;i<n;i++){
            num[i]=input.nextInt();
        }
        int [][]dp=new int[n][2];
        int max=num[0];
        int min=num[0];
        dp[0][0]=num[0];
        dp[0][1]=num[0];
        for(int i=1;i<n;i++){
            dp[i][0]=Math.max(dp[i-1][0]+num[i],num[i]);
            dp[i][1]=Math.min(dp[i-1][1]+num[i],num[i]);
            max=Math.max(max,dp[i][0]);
            min=Math.min(min,dp[i][1]);
        }
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=num[i];
        }
        if(sum-min==0){
            for(int i=0;i<n;i++){
                max=Math.max(max,num[i]);
            }
            System.out.println(max);
        }
        else{
            System.out.println(Math.max(max,sum-min));
        }
    }
}