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

#include <iostream>
#include <vector>

int main()
{
    // f(n):前n个数连续子数组的最大之和
    // f(n) = max(f(n - 1) + nums(n), nums(n))
    // f(1) = nums[0]
    int n;
    std::cin >> n;
    std::vector<int> nums(n);
    for (int i = 0; i < n; ++i)
        std::cin >> nums[i];

    std::vector<int> dp(n);
    dp[0] = nums[0];
    int maxSum = dp[0];
    for (int i = 1; i < n; ++i)
    {
        dp[i] = std::max(dp[i - 1], 0) + nums[i];
        maxSum = std::max(maxSum, dp[i]);
    }
    std::cout << maxSum;
}

#include <iostream>
#include <vector>

int main()
{
    // f(n):前n个数连续子数组的最大之和
    // f(n) = max(f(n - 1) + nums(n), nums(n))
    // f(1) = nums[0]
    int n;
    std::cin >> n;

    int a;
    std::cin >> a;
    int maxSum = a;
    for (int i = 1; i < n; ++i)
    {
        int b;
        std::cin >> b;
        b += std::max(a, 0);
        maxSum = std::max(maxSum, b);
        a = b;
    }
    std::cout << maxSum;
}