1、前言

題目描述

2、思路

主要是一個(gè)轉(zhuǎn)換問(wèn)題，有兩個(gè)case，case1是連續(xù)子數(shù)組都在數(shù)組中；
case2 是連續(xù)子數(shù)組是首尾相連。所以要將 case2轉(zhuǎn)換一下，求最大和，其實(shí)就是求 總和 - 中間部分最小和。

圖解

3、代碼

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int sumMax = 0, max = Integer.MIN_VALUE, sumMin = 0, min = Integer.MAX_VALUE;
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += nums[i];

            // 最大和
            sumMax += nums[i];
            max = Math.max(max, sumMax);
            if(sumMax < 0){
                sumMax = 0;
            }

            // 最小和
            sumMin += nums[i];
            min = Math.min(min, sumMin);
            if(sumMin > 0){
                sumMin = 0;
            }
        }


        return sum - min == 0 ? max : Math.max(max, sum - min);
    }
}