【动态规划4】最大子段和

解题思路

本题要求在一个整数序列中找到一个连续子序列，使得该子序列的和最大。这是一个经典的最大子段和问题，可以通过动态规划的方法高效解决。我们将通过逐步分析，建立状态转移方程，最终找到最优解。

Step1: 讨论 $n=3$ 的情况

假设序列长度 $n=3$，且序列为 $a = [-1, 2, 3]$。我们需要找到该序列中的最大子段和。最大子段和也就是为以i为结尾的最大子段和里的最大值。i取遍所有位置。

所有可能的连续子序列及其和如下：

1. $[-1]$ ：和为 $-1$
2. $[-1, 2]$ ：和为 $1$
3. $[-1, 2, 3]$ ：和为 $4$
4. $[2]$ ：和为 $2$
5. $[2, 3]$ ：和为 $5$
6. $[3]$ ：和为 $3$

从中可以看出，最大子段和为 $5$，对应的子序列为 $[2, 3]$。将这些方案的集合定义为 $D_3$，即 $D_3 = \{ -1, 1, 4, 2, 5, 3 \}$，其中最大值为 $5$。

Step2: 情况分类

为了找到序列中的最大子段和，我们可以将问题分为以下两种情况：

1. 当前元素 $a_i$ 单独作为一个新的子序列的一部分：

   即，当前的最大子段和仅包含 $a_i$ 本身。

2. 当前元素 $a_i$ 作为前一个子序列的一部分：

   即，将 $a_i$ 加入到之前的最大子段和中，形成一个更长的子序列。

通过这两种情况，我们可以决定是否将当前元素加入到之前的子序列中，或者重新开始一个新的子序列。

Step 2：等价映射

在我们求解最大子段和问题时，关键在于如何利用之前已经计算的结果来推算当前的结果。为此，我们循环枚举数组中的每一个元素可以将“当前的元素”的计算通过递推关系与前一个子段和联系起来。

1. 首先，考虑最大子段和等价于 max(dp[i])：
   也就是最大子段和为以i为结尾的最大子段和里的最大值。i取遍所有位置。从这一点出发，我们可以认为每个位置 i 对应着一个子序列，且最大子段和就是以这个位置为结尾的最大子序列的和。

2. 列出以 i 为结尾的所有子段和：

   • 空集 + 当前元素：即把当前元素 a_i 看作是一个新的子序列的起点。此时，子段和为 a_i。
   • 之前的最大子段和 + 当前元素：即当前元素 a_i 连接到前一个子段和上，形成一个新的、更长的子序列。此时，子段和为 dp[i-1] + a_i。

回到n=3的例子看看 1.首先看以第一个元素-1为结尾情况

$[-1]$ ：和为 $-1$

以-1为结尾的最大值是-1只有它自己的情况

2.以第二个元素2为结尾的情况

$[-1, 2]$ ：和为 $1$

$[2]$ ：和为 $2$

显然是把2重新看成一共新的子序列为起点为最优

3.以第三个元素3为结尾的情况

$[-1, 2, 3]$ ：和为 $4$

$[2, 3]$ ：和为 $5$

$[3]$ ：和为 $3$

考虑之前的最大字段和加上当前元素3

从中可以看出，以第一个元素-1结尾的最大值为-1,以第二个元素2为结尾的最大值为2,以第三个元素3为结尾的最大值为5，所以最大字段和为它们三个的最大值max(-1,2,5)，也就是5

Step 3：递推方程的推导

在这种情况下，我们通过比较这两种情况来更新最大子段和。具体来说：

• 空集 + 当前元素：表示当前子段和只包含当前元素 a_i，即 a_i。
• 之前的最大子段和 + 当前元素：表示当前元素 a_i 与前一个子段和结合，即 dp[i-1] + a_i。

例如上面的例子， 对于第二个元素2，也就是

dp[2]=max({[-1]+2[空集]+2})

dp[2]=[2]。 对于第三个元素3，也就是

dp[3]=max({[-1, 2]+3,[-1]+3,[空集]+3})

dp[3]=[2,3]。 因此，递推方程为：

这个方程的含义是：对于当前位置 i，我们选择将 a_i 加入到之前的子序列中，还是将它单独作为一个新的子序列。

Step4: 推广情况

对于任意长度为 $n$ 的序列 $a = [a_1, a_2, \dots, a_n]$，定义 $dp[i]$ 表示以第 $i$ 个元素结尾的最大子段和。根据递推关系，我们有：

通过迭代计算 $dp[i]$，可以逐步找到整个序列的最大子段和。

Step5: 边界条件

在动态规划中，需要明确边界条件来初始化状态转移：

1. 第一个元素的最大子段和：

   $$dp[1] = a_1$$

   因为只有一个元素时，最大子段和就是它本身。

2. 对于 $i > 1$ 的元素：

   使用递推方程：

   $$dp[i] = \max(dp[i-1] + a_i, a_i)$$

这些边界条件确保了动态规划的递推过程有一个明确的起点。

Step6: 总结

1. 状态定义：

   $$dp[i] \quad \text{表示以第 } i \text{ 个元素结尾的最大子段和，即：}$$ $$dp[i] = \max(dp[i-1] + a_i, a_i)$$

2. 状态转移方程：

   $$dp[i] = \max(dp[i-1] + a_i, a_i)$$

3. 边界条件：

   • $$dp[1] = a_1$$

通过动态规划的方法，我们可以高效地计算出序列的最大子段和，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。此外，可以通过优化空间复杂度，将其降低到 $O(1)$，只需使用两个变量来记录当前和之前的子段和。

实现代码

以下是使用 python实现的代码：

# 读取数组的长度
n = int(input())  # 输入一个整数 n，表示数组的长度

# 读取数组元素并转换为整数列表
a = list(map(int, input().split()))  # 输入 n 个整数并存储在列表 a 中

# 在数组前添加一个元素 0，方便后续索引从 1 开始
a = [0] + a  # 现在 a[1] 到 a[n] 是原始数组的元素

# 初始化动态规划数组 dp，长度为 n+1，初始值为 0
dp = [0] * (n + 1)  # dp[i] 表示以第 i 个元素结尾的最大子数组和

# 遍历数组，计算每个位置的最大子数组和
for i in range(1, n + 1):
    # 选择要么将当前元素加入前一个子数组，要么从当前元素重新开始
    dp[i] = max(dp[i - 1] + a[i], a[i])  # 状态转移方程

# 输出所有 dp 值中的最大值，即整个数组的最大子数组和
print(max(dp))  # 输出结果

题目描述：

给定一个整数序列 $a_1, a_2, \dots, a_n$，其中 $n$ 为整数序列的长度。请你计算出该序列的最大子段和，即从该序列中选出一个连续的子序列，使得子序列的和最大。请注意，子序列的长度可以为 1，且可以是整个序列。

输入：

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$，表示序列的长度。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(-10^4 \leq a_i \leq 10^4)$，表示序列中的元素。

输出：

输出一个整数，表示最大子段和。

样例输入：

9
-2 1 -3 4 -1 2 1 -5 4

样例输出：

6

提示：

在上面的例子中，最大子段和为 6，对应的子序列为 $[4, -1, 2, 1]$。