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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int kadane(vector<int>& nums) {
    int maxSum = nums[0];
    int currSum = nums[0];
    
    for(int i = 1; i < nums.size(); i++) {
        currSum = max(nums[i], currSum + nums[i]);
        maxSum = max(maxSum, currSum);
    }
    
    return maxSum;
}

int maxCircularSum(vector<int>& nums) {
    int n = nums.size();
    
    // 计算普通的最大子数组和
    int maxNormal = kadane(nums);
    
    // 如果最大和是负数，说明所有数都是负数
    if(maxNormal < 0) return maxNormal;
    
    // 计算总和
    int totalSum = 0;
    for(int i = 0; i < n; i++) {
        totalSum += nums[i];
        nums[i] = -nums[i];  // 取反用于计算最小子数组和
    }
    
    // 计算环形最大和（总和减去最小子数组和）
    int maxCircular = totalSum + kadane(nums);
    
    return max(maxNormal, maxCircular);
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << maxCircularSum(nums) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static int kadane(int[] nums) {
        int maxSum = nums[0];
        int currSum = nums[0];
        
        for(int i = 1; i < nums.length; i++) {
            currSum = Math.max(nums[i], currSum + nums[i]);
            maxSum = Math.max(maxSum, currSum);
        }
        
        return maxSum;
    }
    
    public static int maxCircularSum(int[] nums) {
        int n = nums.length;
        
        // 计算普通的最大子数组和
        int maxNormal = kadane(nums);
        
        // 如果最大和是负数，说明所有数都是负数
        if(maxNormal < 0) return maxNormal;
        
        // 计算总和
        int totalSum = 0;
        for(int i = 0; i < n; i++) {
            totalSum += nums[i];
            nums[i] = -nums[i];  // 取反用于计算最小子数组和
        }
        
        // 计算环形最大和（总和减去最小子数组和）
        int maxCircular = totalSum + kadane(nums);
        
        return Math.max(maxNormal, maxCircular);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(maxCircularSum(nums));
        sc.close();
    }
}

def kadane(nums):
    max_sum = nums[0]
    curr_sum = nums[0]
    
    for i in range(1, len(nums)):
        curr_sum = max(nums[i], curr_sum + nums[i])
        max_sum = max(max_sum, curr_sum)
    
    return max_sum

def max_circular_sum(nums):
    n = len(nums)
    
    # 计算普通的最大子数组和
    max_normal = kadane(nums)
    
    # 如果最大和是负数，说明所有数都是负数
    if max_normal < 0:
        return max_normal
    
    # 计算总和
    total_sum = sum(nums)
    
    # 计算环形最大和（总和减去最小子数组和）
    nums = [-x for x in nums]  # 取反用于计算最小子数组和
    max_circular = total_sum + kadane(nums)
    
    return max(max_normal, max_circular)

n = int(input())
nums = list(map(int, input().split()))
print(max_circular_sum(nums))