最大连续子序列(序列型DP) 解题日志

最大连续子序列(subsequence)

【问题描述】

给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= K。输出最大连续子序列的和。即求所有连续子序列中元素和最大的一个, 例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和为20。

 

【输入格式】

第1行给出正整数k( <= 1000 ),第2行给出k个整数,中间用空格分隔。

 

【输出格式】

一个整数,表示连续子序列的最大和。

 

【输入样例】

6

-2 11 -4 13 -5 -2

【输出样例】

20

【代码日志】

#include<bits/stdc++.h>
using namespace std;
void FUCK(string name){
	string iii=name+".in";
	string ooo=name+".out";
	freopen(iii.c_str(),"r",stdin);
	freopen(ooo.c_str(),"w",stdout);
}
int n,ans=-99999999;
int ni[100500],dp[100500];
int main(){
	//FUCK("subsequence");
	cin>>n;
	memset(dp,-1,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++){
		cin>>ni[i];
		dp[i]=ni[i]+dp[i-1]>ni[i] ? ni[i]+dp[i-1] : ni[i];
		//cout<<dp[i]<<endl;
		if(ans<dp[i]){
			ans=dp[i];
		}
	}
	//program here
	cout<<ans<<endl;
	return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注