动态规划---hdu1231---最大连续子序列
发布日期:2022-02-02 02:58:07 浏览次数:3 分类:技术文章

本文共 1309 字,大约阅读时间需要 4 分钟。

Problem Description
给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ..., 
Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个, 
例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和 
为20。 
在今年的数据结构考卷中,要求编写程序得到最大和,现在增加一个要求,即还需要输出该 
子序列的第一个和最后一个元素。
 

Input
测试输入包含若干测试用例,每个测试用例占2行,第1行给出正整数K( < 10000 ),第2行给出K个整数,中间用空格分隔。当K为0时,输入结束,该用例不被处理。
 

Output
对每个测试用例,在1行里输出最大和、最大连续子序列的第一个和最后一个元 
素,中间用空格分隔。如果最大连续子序列不唯一,则输出序号i和j最小的那个(如输入样例的第2、3组)。若所有K个元素都是负数,则定义其最大和为0,输出整个序列的首尾元素。 
 

Sample Input
6-2 11 -4 13 -5 -210-10 1 2 3 4 -5 -23 3 7 -2165 -8 3 2 5 01103-1 -5 -23-1 0 -20
 

Sample Output
20 11 1310 1 410 3 510 10 100 -1 -20 0 0
代码实现:

#include
   
    #include
    
     using namespace std;#define MAX 10007int main(){
     
int dp[ MAX ] ;
int n ;
while( cin>>n )
{
if(n==0)break;
int sum = 0 ;
int temp= 0;
int begin;
int end;
int Maxnum=-99999;
for(int i = 0 ; i < n ; i++ )
{
cin>>dp[i];
sum += dp[ i ] ;
if( sum < 0 )
{
temp= i + 1 ;
sum=0;
}
else
{
if( Maxnum < sum )
{
Maxnum = sum ;
begin = temp;
end=i;
}
}
}
if( Maxnum < 0 )
{
cout<<"0 "< <<" "< <
}
else
cout< <<" "< <<" "< <
}
return 0 ;}


转载地址:https://blog.csdn.net/u010368749/article/details/18980763 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:二叉树
下一篇:HDU 动态规划(46道题目)倾情奉献~ 【只提供思路与状态转移方程】

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.249.68.14]2022年05月25日 08时21分37秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章