游泳池建设有专门的网站吗,最近的新闻事件,瑞安人才网,开网页死机文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴线性DP一、题目
1、原题链接 1051. 最大的和 2、题目描述 对于给定的整数序列 A{a1,a2,…,an}#xff0c;找出两个不重合连续子段#xff0c;使得两子段中所有数字的和最…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴线性DP一、题目
1、原题链接 1051. 最大的和 2、题目描述 对于给定的整数序列 A{a1,a2,…,an}找出两个不重合连续子段使得两子段中所有数字的和最大。 我们如下定义函数 d(A) 我们的目标就是求出 d(A)。 输入格式 第一行是一个整数 T代表一共有多少组数据。 接下来是 T 组数据。 每组数据的第一行是一个整数代表数据个数据 n第二行是 n 个整数 a1,a2,…,an。 输出格式 每组数据输出一个整数占一行就是 d(A) 的值。 数据范围 1≤T≤30,2≤n≤50000,|ai|≤10000 输入样例 1
10
1 -1 2 2 3 -3 4 -4 5 -5输出样例 13样例解释 在样例中我们取{2,2,3,-3,4}和{5}两个子段即可得到答案。 二、解题报告
1、思路分析 思路来源y总讲解视频 y总yyds 1利用求单段连续子段和的方法将所有子段和处理出来。 2单段连续子段和最大求解方法
dp[i]表示以a[i]结尾的所有连续子段和的最大值。可以将dp[i]分为两部分①只包含a[i]②不仅包含a[i]还包含a[i]之前的某些数。可知这两部分和分别为a[i]和dp[i-1]a[i]。所以转移方程为 dp[i]max(a[i],dp[i-1]a[i])即dp[i]max(0,dp[i-1])a[i]。
3对数组序列进行 前后缀分解利用g[i]记录所有从1 ~ i中的最大子段和h[i]记录所有从i ~ n中的最大子段和。 4枚举i的所有取值两个连续子段的最大和即为g[i]h[i1]的最大值。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
#include iostream
#include algorithm
using namespace std;
const int N50010,INF1e9;
int a[N],h[N],g[N],dp[N];
int T,n;
int main(){cinT;while(T--){cinn;for(int i1;in;i) cina[i];dp[0]g[0]-INF; //非法状态设置为负无穷//正着求一遍单段连续子段和for(int i1;in;i){dp[i]max(dp[i-1],0)a[i]; //单段连续子段和的转移方程 g[i]max(g[i-1],dp[i]); //g[i]存储前1~i中子段和的最大值如果1~i中的子段和最大值dp[i]比1~i-1中连续子段和最大值g[i-1]大则g[i]dp[i]否则g[i]g[i-1]}dp[n1]h[n1]-INF; //非法状态设置为负无穷//倒着求一遍单段子连续段和for(int in;i1;i--){dp[i]max(dp[i1],0)a[i]; //单段连续子段和的转移方程h[i]max(h[i1],dp[i]); //h[i]存储i1~n中连续子段和的最大值类似g[] }int ans-INF; //两段子段和的最大值可能是负数所以将ans初始化为负无穷//遍历i的取值找到两段连续子段和的最大值for(int i1;in;i) ansmax(ans,g[i]h[i1]);coutansendl;}return 0;
}三、知识风暴 线性DP
