求最大连续子序列,连续子序列和的最大值
目录1标题2分析2.1含义2.2想法3参考代码
1题目问题A:最大连续子序列
[提议者：外部进口]
时间限制：1.000秒内存限制：32 MB
标题描述
给定一个k整数序列{N1，N2，…，NK}，任何连续子序列都可以表示为{Ni，Ni ^ 1，…，Nj}，其中1=i=j=k，最大连续子序列是所有连续子序列的最大元素和。例如，给定序列{-2，11，-4，13，-5，-2}，其最大连续子序列为{11，-4，13}，最大和为20。现在添加一个要求，这个子序列的第一个和最后一个元素也需要输出。
投入
输入包含几个测试用例，每个用例占据2行。第一行给出正整数K( K=10000)，第二行给出K个整数，用空格隔开，每个数的绝对值不超过100。当k为0时，输入结束，用例不被处理。
输出
对于每个测试用例，在一行中输出最大和与最大连续子序列的第一个和最后一个元素，用空格分隔。如果最长的连续子序列不是唯一的，则输出具有最小序列号I和J的序列(例如第二组和第三组输入样本)。如果所有k个元素都为负，则最大和定义为0，输出整个序列的第一个和最后一个元素。
样本输入副本
五
-3 9 -2 5 -4
三
-2 -3 -1
0
样本输出副本
12 9 5
0 -2 -1
2.1求最大连续子序列。
2.2思路提示
这是一个稍微有点困难的动态规划问题。
首先能想到的是枚举每个区间的和，预处理sum[i]来表示区间[1，i]的和，然后通过减法就可以得到O(1)时间内区间[i，j]的和，所以这个方法的时间复杂度是O(n ^ 2)。
那么这个问题的数据范围较大，AC之前还需要进一步优化。记住第I个元素是a[i]，定义dp[i]为后面标签I末尾区间的最大和，那么dp[i]的计算有两个选择，一个是包含a[i-1]，一个是不包含a[i-1]，前者的最大值是dp[i-1] a[i]，后者的最大值是。两者的区别在于dp[i-1]是否大于0。
3参考代码#包括
#包括
使用STD:max；
const int MAXN=10010
int A[MAXN]；
int DP[MAXN]；
int start[MAXN]；
int main(int argc，char const *argv[])
{
int n；
scanf(%d ，n)；
而(n！=0){
int flag=false
for(int I=0；I n；我)
{
scanf(%d ，A[I])；
if(A[i]=0){
flag=true
}
}
if(flag==false){
printf(0 %d %d\n ，A[0]，A[n-1])；
}否则{
//边界
DP[0]=A[0]；
start[0]=0；
for(int I=1；I n；我)
{
if(A[i] A[i] dp[i-1]){
DP[I]=A[I]DP[I-1]；
start[I]=start[I-1]；
}否则{
DP[I]=A[I]；
start[I]=I；
}
}
int index=0；
for(int I=1；I n；我)
{
if(dp[index] dp[i]){
index=I；
}
}
printf(%d %d %d\n ，dp[index]，A[start[index]]，A[index])；
}
scanf(%d ，n)；
}
返回0；
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。