1.起点与终点未知,求整个序列的最大子序列和:
int i; maxSum = a[0]; /* 开始循环求子序列和 */ for (i = 0; i < len; i++) { curSum = curSum + a[i]; /* 与最大子序列和比较,更新最大子序列和 */ if (curSum > maxSum) maxSum = curSum; /* 动态规划部分,舍弃当前和为负的子序列 */ if (curSum < 0) curSum = 0; } printf("%d\n",maxSum);
2.含右边界的最大子序列和(就是说已知终点从后往前找和的最大值):
int i; int sum = 0; int maxSum = a[right]; for (i = right; i >= left; i--) { sum += a[i]; if (sum > maxSum) maxSum = sum; } printf("%d\n",maxSum);
3.从含左边界的最大子序列和(就是说已知起点从前往后找和的最大值):
int i; int sum = 0; int maxSum = a[left]; for (i = left; i <= right; i++) { sum += a[i]; if (sum > maxSum) { maxSum = sum; } } printf("%d\n",maxSum);
注意:
以上总结与F题稍有不同,注意到开头maxsum的赋值,上面的全部算最大子序列和的解法都初始值为第一个元素的值,但是F题初始值为0。因为F题在于算出一个最大连续的正数和出来,如果找不到就默认为0,上面解法是默认为第一项。
NYOJ:
44-子串和:
#include<stdio.h> int main() { int N,sum,max,number,M; scanf("%d",&N); while(N--) { scanf("%d",&M); scanf("%d",&number); sum=number; max=number; //初始值默认为第一项,不是0,说明最大子串和可以为负数 M--; while(M--) { scanf("%d",&number); if(sum<0) sum=number; //动态规划部分,小于0则舍去前面 //不应该是判断下一个number该加不加,number是必须要加的数 //有两种可能,要不就是前面积累了连续的几个数到这个number数时继续积累,要不就是前面的不要,从他开始积累 //总言而知,number要不是它被积累(sum>0的时候),要不就是它积累其他数(sum<0的时候) else sum+=number; if(sum>max) max=sum; } printf("%d\n",max); } return 0; }
这题与F题有点区别。
F题中的错误:
i=0; while(number[i]<0) i++; //先忽略前面的负数项,从正数项开始求 for(i;i<N;i++) { sum1+=number[i]; if(sum1>max) max=sum1; }
如果这样写的话,那么就已经规定了从第一个非负数开始向后加和了。
如果存在序列-1,-2,2,3,-5,-6,10000,-7,-8
那么如果按照这样写的话(本质就是3的写法),最大子序列和就为9994,
但是实质上起点应该是不确定的,最大子序列应该是10000才对(本质就是1的写法)。
所以F题出现了错误按照这个序列的话输出的正确答案应该是10024
但是如果按照上面这个写法的话就是10012,从而验证出这个的写法在F题是不成立的。
动态规划求最大连续子序列和:
定义max[x]为包含a[x]的序列(a[1],...,a[x])的最大子序列的和,则 max[x+1]= max[x]>0?max[x]+a[x+1]:a[x+1];
下面分析max[x+1] = max[x]>0?max[x]+a[x+1]:a[x+1]:
首先要明白,无论是否要加上max[x],在max[x+1]中,a[x+1]是一定要加上的;若max[x]<0,则无论a[x+1]大于零还是小于零max[x]+a[x+1]<a[x+1],所以,出于该原因,当max[x]<0时,max[x+1]=a[x+1];而若max[x]>0,则无论a[x+1]是大于零还是小于零,均有max[x]+a[x+1]>a[x+1];所以,若为该种情况,max[x+1]=max[x]+a[x+1](注意:再次提醒,a[x+1]是一定要加上的,所以判断是否小于0应该是判断max[i]而不是a[x+1])。
F题动态规划解法:
#include<stdio.h> int number[100005]; int max[100005]; int main() { int N,i,m,sum=0; scanf("%d",&N); for(i=0;i<N;i++) { scanf("%d",&number[i]); sum+=number[i]; } max[0]=number[0]; m=0;//一开始只能初始化为0 //如果不初始化为0,而是初始化为max[0]的话 //当序列为-1,-2,-3的时候,最大一直为-1,最后输出的结果是4而不是6了 for(i=1;i<N;i++) { max[i]=max[i-1]>=0?max[i-1]+number[i]:number[i]; if(max[i]>m) m=max[i]; //该处存在盲点,第一项没对比到,即max[0] } if(max[0]>m) m=max[0]; //另外比完后再对比一次第一项 //测试 // printf("\n"); // for(i=0;i<N;i++) // printf("%d ",max[i]); // printf("\n"); printf("%d\n",2*m-sum); return 0; }
相关推荐
2.采用分治法求解最大连续子序列和问题 给定一个有n(n≥1)个整数的序列,要求求出其中最大连续子序列的和。 例如: 序列(-2,11,-4,13,-5,-2)的最大子序列和为20序列; (-6,2,4,-7,5,3,2,-1,6,...
解法1—O(N^2)解法 解法2—O(NlgN)解法 解法3—O(N)解法 可以直接在记事本运行
动态规划——最大连续子序列和一维最大连续子序列和[x] LeetCode 53 Maximum Subarray设$d[i]$表示以序列中$s[i]$结尾的最大
文件给出了四种方式求解子序列的最大和,并给出了具体的代码实现。对于深入探讨算法和程序性能非常有帮助。
主要介绍了Python语言描述最大连续子序列和,具有一定借鉴价值,需要的朋友可以了解下。
NULL 博文链接:https://shmilyaw-hotmail-com.iteye.com/blog/1616632
题目是标准的ACM竞赛题,word文档里包含求最大连续子序列的题目和完整的实验代码,并在VC6.0上运行通过!!!
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)
三种方法实现最大子序列,时间复杂度分别是O(n^3),o(n^2),o(n)
C++求最大子序列的和 问题:求一个数组 / 序列的满足条件的子数组 / 子序列。 条件: 1. 子数组必须是连续的。 2. 求和即可,不需要返回子数组是哪段。 3. 数组元素为整数。
一个整数序列,求最大子序列的和,C++,The max sub sum of an array.
算法设计与分析中最大子段和问题的蛮力法、分治法和动态规划法
算法系列之六:最长公共子序列(LCS)问题(连续子序列)的三种解法.doc
数组 求连续子序列最大和程序 时间复杂度O(n) 空间复杂度O(1)
把一个包含n个正整数的序列划分成m个连续的子序列,每个整数刚好属于一个序列。设第i个序列的各数之和是S(i)。要求:让所有的S(i)的最大值尽量小。例如:序列1,2,3,2,5,4划分成3个序列的最优方案为123|25|4,...
主要介绍了利用C语言来求最大连续子序列乘积的方法,基本的思路以外文中还附有相关ACM题目,需要的朋友可以参考下
动态规划解最大自序列和经典DP算法 最大连续子序列
js代码-数组的最大不重复连续子序列