hdu1231 最大连续子序列--DP-白红宇的个人博客

hdu1231 最大连续子序列--DP

发布日期：2021-10-03 20:31:49 浏览次数：13 分类：技术文章

本文共 1751 字，大约阅读时间需要 5 分钟。

原题链接：

一：原题内容

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   
       
         
     Hint    
    Hint   
      
    Huge input, scanf is recommended.

二：分析理解

直接上代码吧。。。。

三：AC代码

#include
   
    #include
    
     #include
     
      using namespace std;int a[10005];int main(){	int N;	while (scanf("%d", &N) && N)	{		for (int i = 0; i < N; i++)			scanf("%d", &a[i]);		int max = a[0];		int cnt = a[0];		int left = a[0];		int right = a[0];		int flag = a[0];		for (int i = 1; i < N; i++)		{			if (cnt < 0)			{				flag = a[i];				cnt = a[i];			}			else				cnt += a[i];			if (cnt > max)			{				left = flag;				right = a[i];				max = cnt;			}		}		if (max < 0)		{			printf("%d %d %d\n", 0, a[0], a[N - 1]);			continue;		}		printf("%d %d %d\n", max, left, right);	}		return 0;}

#include
   
    #include
    
     using namespace std;int dp[100]; //表示以i为尾的最大连续子序列int N;int sum;int main(){	while (cin >> N)	{		for (int i = 0; i < N; i++)			cin >> dp[i];				if (dp[0] < 0)  //初始化			dp[0] = 0;		int sum = dp[0];		for (int i = 1; i < N; i++)		{			if (dp[i] + dp[i - 1] >= 0)			{				dp[i] += dp[i - 1];				if (dp[i] > sum)					sum = dp[i];			}			else				dp[i] = 0;		}		cout << sum << endl;	}}

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

上一篇：hdu1003 Max Sum--DP

下一篇：hdu3068 最长回文--Manacher算法

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章