最大子段和问题：算法详解及C++代码实现

题目描述

给定一个长为 n 的序列，任意选择其中连续的 x（0 <= x <= n）项所确定的一段更短的连续序列叫作一个子段。 一个子段的得分为其每个元素之和，请求出原序列的最大子段和。

输入格式

从标准输入读入数据。 第一行一个正整数 n（1 <= n <= 10^6），代表序列长度。 第二行输入 n 个整数 a[i]（|a[i]| <= 10^6），为序列元素。

输出格式

输出到标准输出。 输出一个整数，代表最大子段和。

样例 #1

样例输入 #1

6
1 -2 4 -2 -1 4

样例输出 #1

5

算法思路

该问题可以使用动态规划来解决。我们可以定义 dp[i] 表示以 a[i] 结尾的最大子段和。 那么，dp[i] 的值可以由以下两种情况决定：

1. dp[i - 1] + a[i]：即包含 a[i] 的最大子段和。
2. a[i]：即仅包含 a[i] 的最大子段和。

最终，dp 数组中的最大值即为原序列的最大子段和。

C++ 代码实现

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int a[N], dp[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    dp[1] = a[1];
    int ans = dp[1];
    for (int i = 2; i <= n; i ++ )
    {
        dp[i] = max(dp[i - 1] + a[i], a[i]);
        ans = max(ans, dp[i]);
    }

    printf("%d\n", ans);

    return 0;
}

代码解析

1. dp[1] = a[1]：初始化 dp 数组的第一个元素为 a[1]。
2. for 循环遍历数组 a，计算每个位置的最大子段和。
3. dp[i] = max(dp[i - 1] + a[i], a[i])：根据动态规划的思路，计算 dp[i] 的值。
4. ans = max(ans, dp[i])：更新最大子段和 ans 的值。

总结

最大子段和问题是一个经典的动态规划问题，我们可以通过定义 dp 数组来记录以每个元素结尾的最大子段和，最终得到原序列的最大子段和。

希望本文能够帮助您理解和解决最大子段和问题。