动态规划---线性dp1

7-3 最大子序列总和

给定 K 个整数序列 { N1， N2， ...， NK }。连续子序列定义为 { Ni， Ni+1， ...， Nj }，其中 1 ≤ i ≤ j ≤ K。最大子序列是具有最大元素总和的连续子序列。例如，给定序列 { -2， 11， -4， 13， -5， -2 }，其最大子序列为 { 11， -4， 13 }，最大和为 20。

现在，您应该找到最大的总和，以及最大子序列的第一个数字和最后一个数字。

输入规格:

每个输入文件都包含一个测试用例。每个案例占用两行。第一行包含正整数 K （≤10000）。第二行包含 K 个数字，用空格分隔。

输出规格:

对于每个测试用例，在一行中输出最大总和，以及最大子序列的第一个和最后一个数字。数字必须用一个空格分隔，但行尾不得有多余的空格。如果最大子序列不唯一，则输出索引 i 和 j 最小的子序列（如示例案例所示）。如果所有 K 个数都是负数，则其最大和被定义为 0，并且您应该输出整个序列的第一个和最后一个数字。

Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

解答

• f[i]表示以i结尾的最大字段和
• l[i]表示这段子段和的左边界，r[i]表示这段子段和的有边界
• 易错点没考虑到0，最大值没问题，但是边界有问题

#include <iostream>
using namespace std;
const int N = 1e4 + 10;
int a[N], f[N];
int l[N], r[N];
int n;

int main()
{
    cin >> n;
    bool flag = false;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if(a[i] >= 0) flag = true;
    }

    for(int i = 1; i <= n; i++)
    {
        f[i] = max(f[i - 1] + a[i], a[i]);

        if(f[i] == a[i])
            l[i] = a[i],r[i] = a[i];
        else 
            l[i] = l[i - 1], r[i] = a[i];

        if(f[i - 1] == 0 && i != 1) l[i] = l[i - 1];
    }

    int ans = 0;
    int ll =  0,rr = 0;
    for(int i = 1; i <= n; i++)
    {
        if(f[i] > ans)
        {
            ans = f[i];
            ll = l[i];
            rr = r[i];
        }
    }

    if(flag) cout << ans << " " << ll << " " << rr;
    else cout << 0 << " "<< a[1] << " " << a[n];
    return 0;
}