模板题——连续子序列和的最大值

题目：

给定一个长度为 n 的整形数组 nums，求从数组索引 l 至 索引 r 的整数序列中，连续序列和的最大值为多少。

思路：

本题的主要思路，可分为两种

1. 使用遍历的思想，遍历出序列的每种情况，逐一求和，计算最大值

但这种思路及其耗费时间,不可取。

2. 使用动态规划的思想，使用一个数组 dp 记录，从索引 l 起包含位置 k 连续序列和的最大值 （l<=k<=r），最大值可由下面的公式推导。

dp[k] = max{ num[k] , num[k] + dp[k-1] }

公式解释：

1. 这个公式的意思很明了，即某个位置之前的序列和若为正，那么包含之前的序列，肯定会使包含当前位置的序列和增大。
2. 这个公式不好理解之处在于，若一个位置的值为负还要包括他吗？举个例子来说明：
   1. 若位置 i 处值为负，之前序列和为正，那么虽然包括了他使到这个位置为止的序列和减小，但是起到了连接 i+1 位置的作用，若 i+1 位置的值很大，那么包含 i 位置使序列和减小的损失就可以忽略了，因为到 i+1 处的序列和是增大的了。
   2. 若之前序列和为负，那么包含之前序列就没有任何意义，到 i 位置的序列和的最大值，就是位置 i 的值。
3. 数组 dp 中记录的是包含位置 i 后的序列的最大值，那么在将所有位置进行计算后，取 dp 数组中的最大值，即是整个序列中子序列和的最大值。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n + 1);
    vector<int> max_sum(n + 1);

    for (int i = 1; i <= n; ++i)
    {
        cin >> nums[i];
    }

    int l, r, sum;
    cin >> l >> r;

    sum = nums[l] = max_sum[l];
    for (int j = l + 1; j <= r; ++j)
    {
        max_sum[j] = max(nums[j], nums[j] + max_sum[j - 1]);
        if (sum < max_sum[j])
            sum = max_sum[j];
    }
    cout << sum << endl;

    return 0;
}

优化

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n + 1);

    for (int i = 1; i <= n; ++i)
    {
        cin >> nums[i];
    }
    int l, r, sum, result;

    cin >> l >> r;

    result = sum = nums[l];

    for (int j = l; j <= r; ++j)
    {
        sum = max(nums[j], sum + nums[j]);
        result = max(result, sum);
    }
    cout << result << endl;

    return 0;
}