最大子数组和循环数组 java代码

最大子数组和问题可以使用Kadane算法来解决，它的时间复杂度是O(n)。具体思路是：从左到右遍历数组，对于每个元素，计算包含该元素的最大子数组和，并更新全局最大子数组和。在计算包含该元素的最大子数组和时，可以使用动态规划的思想，即当前元素的最大子数组和为它自身和前面元素的最大子数组和的和。

循环数组也可以使用Kadane算法来解决，具体思路是将原数组复制一份接在后面，形成一个长度为2n的新数组，然后在新数组上执行Kadane算法，但要注意最大子数组可能跨越原数组和复制数组的分界线，需要特殊处理。

以下是Java代码实现：

public static int maxSubArray(int[] nums) {
    int maxSum = nums, curSum = 0;
    for (int num : nums) {
        curSum = Math.max(curSum + num, num);
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
}

public static int maxSubArrayCircular(int[] nums) {
    int maxSum1 = maxSubArray(nums);
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        nums[i] = -nums[i];
    }
    int maxSum2 = sum + maxSubArray(nums);
    return Math.max(maxSum1, maxSum2);
}