动态规划最大子段和讲解和【题解】——最大子段和

1.详细讲解

最大子段和

题目描述

给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 $n$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

7
2 -4 3 -1 2 -4 3

输出 #1

4

提示

样例 1 解释

选取 $[3,5]$ 子段 { 3 , − 1 , 2 } \{3, -1, 2\} {3,−1,2}，其和为 $4$。

数据规模与约定

• 对于 $40\%$ 的数据，保证 $n\le 2\times 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^5$，$-10^4\le a_i\le 10^4$。

1.1.思路解析

    题目已经在上面讲得很清楚了，我就不再赘述。这里直接来一个动态规划五步走。

1.明确问题：如上。
2.状态：dp[i]表示以第$i$个元素结尾的最大子段和。
3.初始条件：dp[1]=a[1]。
4.状态转移方程：
$$dp[i]=max(a[i],dp[i-1]+a[i])$$
5.答案：$max(dp[i])(i\in [1,n])$。

    首先，问题和状态不用过多解释。

    再来看看初始条件，很明显，第一个数前面没有可以接的数了，直接赋值。

    然后是状态转移方程，这里运用了一点贪心的思想。对于当前数，如果接上前面的数还不如直接使用这一个数，就直接赋值，否则取上前面的数。

    最后是答案。和最长上升子序列一样，最大的子段和有可能是以任意一个数结尾的。在转移状态时，我们就可以将当前状态与ans取个较大值。

1.2.AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010//题目中n的数据范围,可以根据实际情况更改
int main() {int dp[MAXN], a[MAXN], n, ans = INT_MIN;//ans先赋一个较小值cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];dp[1] = a[1];//初始状态for (int i = 2; i <= n; i++) {dp[i] = max(a[i], dp[i - 1] + a[i]);//状态转移方程ans = max(ans, dp[i]);}cout << ans;return 0;
}

2.优化

    容易发现，每一次循环都只用到了当前的a[i]和dp[i-1]。我们可以只使用两个变量存储dp[i-1]和a[i]，示例如下：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010//题目中n的数据范围,可以根据实际情况更改
int main() {int dp, n, ans = INT_MIN;//ans先赋一个较小值cin >> n;for (int i = 1; i <= n; i++) {int tmp;cin >> tmp;if (i == 1) {//初始状态 dp = tmp;continue;}dp = max(tmp, dp + tmp);//状态转移方程 ans = max(ans, dp);}cout << ans;return 0;
}

3.别言

    此题还有许多的做法，例如前缀和，还有分治。因为篇幅关系。这里就不做详细讲解。感兴趣的同学可以去看看这里。

喜欢就订阅此专辑吧！

【蓝胖子编程教育简介】
蓝胖子编程教育，是一家面向青少年的编程教育平台。平台为全国青少年提供最专业的编程教育服务，包括提供最新最详细的编程相关资讯、最专业的竞赛指导、最合理的课程规划等。本平台利用趣味性和互动性强的教学方式，旨在激发孩子们对编程的兴趣，培养他们的逻辑思维能力和创造力，让孩子们在轻松愉快的氛围中掌握编程知识，为未来科技人才的培养奠定坚实基础。

欢迎扫码关注蓝胖子编程教育