题解 | #最大连续子序列#

忽略规范的输入方式，只处理一次

写于2024.3.17，祝复试顺利

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10000;
int a[maxn];
int dp[maxn]; // dp[i]组代表以i为结尾的最大连续子序列

int maxsubstr(int n) // 对数组maxsubstr中前n个数进行  找最大连续子序列
{
    int i;
    int maximum = 0;
    for (i = 0; i < n; i++)
    {
        if (i == 0)
            dp[i] = a[i];
        else
            dp[i] = max(a[i], dp[i - 1] + a[i]); // 状态拓展函数
        maximum = max(maximum, dp[i]);
    }
    return maximum;
}

int main()
{
    int n, i, answer, zancun, j;
    scanf("%d", &n);
    // while (n != 0)
    // {
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }

    for (i = 0; i < n; i++)
    {
        if (a[i] >= 0)
            break;
    }
    if (i == n) // 如果全是负数则输出头尾
    {
        cout << '0' << ' ' << a[0] << ' ' << a[n - 1] << endl;
        return 0;
    }
    // 不全负则继续判断
    answer = maxsubstr(n);
    cout << answer << ' ';
    for (i = 0; i < n; i++)
    {
        if (dp[i] == answer)
        {
            zancun = a[i];
            break;
        }
    }
    if (a[i] == answer)
        j = i;
    else
    {
        for (j = i - 1; j >= 0; j--) // 从i-1位置往前找子序列的第一个元素
        {
            zancun += a[j];
            if (zancun == answer)
            {
                break;
            }
        }
    }

    cout << a[j] << ' ' << a[i] << endl;

    // scanf("%d", &n);
    // cin >> n;
    // cout << "hdu" << n << endl;
    // }

    return 0;
}