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

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

int main() {
    int buf, n;
    cin >> n;
    vector<int> nums;
    while (cin >> buf) {
        nums.push_back(buf);
    }

    // int maxSum = nums[0], minSum = 0, curSum = 0;
    // vector<int> curSums; // 保存当前连续子数组和(当前总前缀和)
    // for(int i = 0; i < n; ++i) {
    //     curSum += nums[i];
    //     curSums.push_back(curSum);
    //     maxSum = std::max(maxSum, curSum - minSum);
    //     minSum = std::min(minSum, curSum);
    // }

    // int maxSum = nums[0], minSum = min(0, nums[0]), curSum = nums[0];
    // for(int i = 1; i < n; ++i) {
    //     curSum += nums[i];
    //     maxSum = max(maxSum, curSum - minSum);
    //     minSum = min(minSum, curSum);
    // }

    // int maxSum = INT_MIN, minSum = 0;
    // vector<int> curSums;
    // for(int i = 0; i < n; ++i) {
    //     if(i) {
    //         curSums.push_back( nums[i] + curSums[i - 1] );
    //     } else curSums.push_back(nums[i]);
    //     maxSum = std::max(maxSum, curSums[i] - minSum);
    //     minSum = std::min(minSum, curSums[i]);
    // }

    // int maxSum = nums[0], minSum = min(0, nums[0]);
    // vector<int> curSums = {nums[0]};
    // for(int i = 1; i < n; ++i) {
    //     curSums.push_back( curSums[i - 1] + nums[i] );
    //     maxSum = std::max(maxSum, curSums[i] - minSum);
    //     minSum = std::min(minSum, curSums[i]);
    // }

    int maxSum = nums[0], curSum = nums[0];
    for (int i = 1; i < n; ++i) {
        curSum = std::max(nums[i], curSum + nums[i]);
        maxSum = std::max(maxSum, curSum);
    }

    cout << maxSum << endl;

    return 0;
}