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

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] dp1= new int[n];
        int[] dp2 = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = sc.nextInt();
        }
        // dp[i]:以i结尾最大和 dp[i] = Math.max(dp[i-1]+arr[i],arr[i]);
        // 循环 -  dp[i%n] = Math.max(dp[(i-1)%n]+arr[i%n],arr[i%n]) 不行无法确定结束位置
        // 然后
        /*
        最大连续子数组和最小连续子数组 
        一定是相连的两部分。否则中间不相连的部分属于?
        求得如果最大连续和和最小连续和相加小于总和。说明数组两边的端点是正值,没有符合循环数组要求，通过最小连续和求
        */
        dp1[0]=arr[0];
        dp2[0]=arr[0];
        int sum, max_len,min_len;
        sum=max_len =min_len= arr[0];
        for(int i=1;i<n;i++) {
            dp1[i] = (int)Math.max(dp1[i-1]+arr[i], arr[i]);
            dp2[i] = (int)Math.min(dp2[i-1]+arr[i], arr[i]);
            max_len = Math.max(max_len, dp1[i]);
            min_len = Math.min(min_len, dp2[i]);
            sum += arr[i];
        }
        if(max_len>=0 && max_len + min_len < sum) max_len = sum - min_len;
        System.out.println(max_len);
    }
}