- 浏览: 70738 次
- 性别:
- 来自: 杭州
最新评论
问题描述:给定一个序列a[1],a[2]...a[n],求解其连续子序列中元素和的最大值
例如: 6 -1 5 4 -7 这个序列最大连续子序列和为14
具体问题见: HDOJ 1003 TZU 1202
这个问题在《数据结构与算法分析--c语言描述》(weiss著)中文版第13页(英文版第18页)中也有描述。在第21页给出了一个算法程序:
我将算法写成了下面的样子:
此时必须将else这个关键字删除,这是因为使用了不同的值来初始化变量引起的。书本中的例子能够始终保证MaxSum为非负值。而我改写后的算法在很多情况下MaxSum都会是负数
我的acm程序如下(在上面两个网站都是ac):
程序主要部分还是上面的算法,只是加上了对子序列首尾索引号的处理。
例如: 6 -1 5 4 -7 这个序列最大连续子序列和为14
具体问题见: HDOJ 1003 TZU 1202
这个问题在《数据结构与算法分析--c语言描述》(weiss著)中文版第13页(英文版第18页)中也有描述。在第21页给出了一个算法程序:
int MaxSubsequenceSum(const int A[], int N) { int ThisSum,MaxSum,j; ThisSum = MaxSum = 0; for(j = 0; j < N; j++) { ThisSum += A[j]; if(ThisSum > MaxSum) MaxSum = ThisSum; else if(ThisSum < 0) ThisSum = 0; } return MaxSum; }
我将算法写成了下面的样子:
int MaxSubsequenceSum(const int A[], int N) { int ThisSum,MaxSum,j; ThisSum =0, MaxSum =INT_MIN; for(j = 0; j < N; j++) { ThisSum += A[j]; if(ThisSum > MaxSum) MaxSum = ThisSum; if(ThisSum < 0) ThisSum = 0; } return MaxSum; }
此时必须将else这个关键字删除,这是因为使用了不同的值来初始化变量引起的。书本中的例子能够始终保证MaxSum为非负值。而我改写后的算法在很多情况下MaxSum都会是负数
我的acm程序如下(在上面两个网站都是ac):
#include <stdio.h> #include <limits.h> #define MAX 100000+100 int main(void) { int n; int m; int a[MAX]; int i,j; int thisSum,maxSum; int maxStart,maxEnd,thisStart; scanf("%d",&n); for(i = 1; i <= n; i++) { scanf("%d",&m); for(maxStart=maxEnd=thisStart=thisSum=0,maxSum=INT_MIN,j = 0; j < m; j++) { scanf("%d",&a[j]); thisSum += a[j]; if(thisSum > maxSum) { maxSum = thisSum; maxStart = thisStart; maxEnd = j; } if(thisSum < 0) { thisSum = 0; thisStart = j+1; } } if(i > 1) printf("\n"); printf("Case %d:\n",i); printf("%d %d %d\n",maxSum,maxStart+1,maxEnd+1); } return 0; }
程序主要部分还是上面的算法,只是加上了对子序列首尾索引号的处理。
发表评论
-
最小c编译器
2011-11-08 14:09 1427最小c编译器(来源 (最好在linux下操作))代码有好几个 ... -
the development of c language(转)
2011-11-08 09:25 1122c语言之父Dennis Ritchie 写的关于c语言开发历 ... -
C语言,你真的弄懂了么?
2011-11-07 12:42 1731程序(来源 ): #include <stdi ... -
pe文件格式实例解析
2011-11-07 10:05 0环境:windows xp 速龙3000+(即x86兼容32位 ... -
小型elf "Hello,World"程序
2011-11-06 23:59 1330参考链接:http://timelessname.com/el ... -
elf文件格式实例解析
2011-11-05 23:00 6287试验环境:archlinux 速龙3000+(即x86兼 ... -
高质量的c源代码
2011-11-03 10:18 1101现在自由软件及开源软件越来越流行,有大量的附带源程序 ... -
fltk 库
2011-09-26 19:47 1774fltk是一个小型、开源、支持OpenGL 、跨平台(win ... -
《Introduction to Computing Systems: From bits and gates to C and beyond》
2011-09-25 23:33 2125很好的一本计算机的入门书,被很多学校采纳作为教材,作者Yale ... -
csapp bufbomb实验
2011-09-16 14:21 4554csapp (《深入理解计算机系统》)一书中有一个关于缓冲区 ... -
the blocks problem(uva 101 or poj 1208)
2011-09-11 20:57 1805题目描述见:uva 101 or poj 1208 ... -
the blocks problem(uva 101 or poj 1208)
2011-09-11 20:56 0题目描述见:uva 101 or poj 1208 ... -
部分排序算法c语言实现
2011-09-02 14:51 993代码比较粗糙,主要是用于对排序算法的理解,因而忽略了边界和容错 ... -
编译器开发相关资源
2011-08-31 08:40 1173开发编译器相关的一些网络资源: how difficu ... -
zoj 1025 Wooden Sticks
2011-07-23 20:25 947题目见:zoj 1025 先对木棒按照长度进行排序,然后再计 ... -
zoj 1088 System Overload
2011-07-23 17:30 1139约瑟夫环 (josephus problem )问题, ... -
zoj 1091 Knight Moves
2011-07-23 09:05 820题目见zoj 1091 使用宽度搜索优先来求解, ... -
zoj 1078 palindrom numbers
2011-07-22 19:31 1122题目见zoj 1078 主要是判断一个整数在基数为2 ... -
zoj 1006 do the untwist
2011-07-22 13:24 904题目见zoj 1006 或poj 1317 简单 ... -
zoj 3488 conic section
2011-07-22 12:23 973题目见zoj 3488 很简单的题目,却没能一次搞定,因 ...
相关推荐
2.采用分治法求解最大连续子序列和问题 给定一个有n(n≥1)个整数的序列,要求求出其中最大连续子序列的和。 例如: 序列(-2,11,-4,13,-5,-2)的最大子序列和为20序列; (-6,2,4,-7,5,3,2,-1,6,...
NULL 博文链接:https://shmilyaw-hotmail-com.iteye.com/blog/1616632
最大连续子序列
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)
文件给出了四种方式求解子序列的最大和,并给出了具体的代码实现。对于深入探讨算法和程序性能非常有帮助。
解法1—O(N^2)解法 解法2—O(NlgN)解法 解法3—O(N)解法 可以直接在记事本运行
题目是标准的ACM竞赛题,word文档里包含求最大连续子序列的题目和完整的实验代码,并在VC6.0上运行通过!!!
主要介绍了Python语言描述最大连续子序列和,具有一定借鉴价值,需要的朋友可以了解下。
C++求最大子序列的和 问题:求一个数组 / 序列的满足条件的子数组 / 子序列。 条件: 1. 子数组必须是连续的。 2. 求和即可,不需要返回子数组是哪段。 3. 数组元素为整数。
算法系列之六:最长公共子序列(LCS)问题(连续子序列)的三种解法.doc
三种方法实现最大子序列,时间复杂度分别是O(n^3),o(n^2),o(n)
动态规划——最大连续子序列和一维最大连续子序列和[x] LeetCode 53 Maximum Subarray设$d[i]$表示以序列中$s[i]$结尾的最大
实验任务包括了多种算法应用场景,如循环赛日程安排、最大连续子序列和问题、0-1背包问题、哈夫曼编码、DNA序列分类等。 在实验设备和工具方面,报告指出了使用的是惠普Win10电脑和Java/Python环境下的eclipse和...
一个整数序列,求最大子序列的和,C++,The max sub sum of an array.
实验任务多样,包括了生命游戏模拟、带锁的门问题、三壶谜题、字符串匹配问题、交替放置的碟子问题以及最大连续子序列和问题等。 在实验设备和工具方面,报告指出了使用的是惠普Win10电脑和Java/Python环境下的...
数组 求连续子序列最大和程序 时间复杂度O(n) 空间复杂度O(1)
实验任务多样,包括模拟生命游戏、对DNA序列进行分类、实现字符串匹配算法、设计循环赛日程安排以及求解最大连续子序列和问题。 在实验设备和工具方面,报告指出了使用的是Win10电脑和Visual Studio或Microsoft ...
把一个包含n个正整数的序列划分成m个连续的子序列,每个整数刚好属于一个序列。设第i个序列的各数之和是S(i)。要求:让所有的S(i)的最大值尽量小。例如:序列1,2,3,2,5,4划分成3个序列的最优方案为123|25|4,...
动态规划解最大自序列和经典DP算法 最大连续子序列