力扣---918. 环形子数组的最大和

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

示例 1：
输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

示例 2：
输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

示例 3：
输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

提示：
    n == nums.length
    1 <= n <= 3 * 104
    -3 * 104 <= nums[i] <= 3 * 104​​​​​​​

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-sum-circular-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

本题和https://www.cnblogs.com/allWu/p/16987669.html这道题的区别在于多了一个首尾相接的条件。

共有两种可能：1. 最大子数组没有用到首尾相接这个条件

                         2. 最大子数组用到了收尾相接这个条件

对第一种情况来说，答案和https://www.cnblogs.com/allWu/p/16987669.html这道题的答案一样。

对第二种情况来说，意味着最小子数组没有用到这个条件。此时，最大子数组等于元素之和减去最小子数组的元素和。

如果数组所有的元素都为负数，那么最大子数组的和必定为负数，此时直接返回最大子数组的和即可。

代码如下：

 1 class Solution {
 2     public int maxSubarraySumCircular(int[] nums) {
 3         //int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
 4         int max = nums[0];
 5         int tem = 0;
 6         int numAdd = 0;
 7         for (int num : nums) {
 8             numAdd += num;
 9             tem += num;
10             max = Math.max(tem, max);
11             if (tem <= 0) {
12                 tem = 0;
13             }
14         }
15         if (max <= 0) {
16             return max;
17         }
18         int min = nums[0];
19         for (int num : nums) {
20             tem += num;
21             min = Math.min(tem, min);
22             if (tem >= 0) {
23                 tem = 0;
24             }
25         }
26         return Math.max(max, numAdd - min);
27     }
28 }

运行结果如下：