一、什么是求最大连续子数列和
首先来看看这是个怎样的问题的,问题描述:一个整型数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和,求所有子数组的和的最大值。注意:当全是负数的情况时,返回最大的那个负数
二、解题思路
这个问题的思路其实非常简单,从左到右扫描数组,在扫描过程中,记录数组的负数的个数和扫描过中数据中的最大值,并累加每个扫描到的数据的和,假设用变量thisSum(初值为0)保存,如果当前的累加值大于之前的累加值的最大值 (例如用变量sum记录,初值为0),则把当前的最大值保存为最大值(sum = thisSum),如果thisSum小于0,则把thisSum设置为0并重新进行累加。一直这样扫描数组,直到把数组扫描完。
由于thisSum已经小于0,也就是说之前统计的和可以舍弃,因为把当前的元素累加之后,结果反而小了。例如把数组分成三部分AiB,因为A的值大于0,A+i的值小于0,所以如果从B开始从新累加,则其值一定比包括i然后去累加B的结果大,因为i小于0,而B中的和却不一定比在A之前累加的和大。
由于如果数组全是负数时,要返回最大的负数,而从上面所说的说法中,我们可以看到当前累加总和(thisSum)总是与0进行比较,如果小于0则把thisSum置为0,所以当数组全是负数时,thisSum和数组的最大子序列之和(sum)总是为0,而与现实有点不一样,所以就要记录负数的数量,当负数的数量等于元素的个数(即全是负数)时,就要把最大连续子序列和置为最大的负数。这也是前面所说的,在扫描过程中记录负数的个数和最大元素的作用。
三、实现代码
int MaxSum(int* a,int n)
{
int sum = 0; //用于记录最大的连续子数组和
int flag = 0;//用于记录负数的个数
int MaxNum = *a;//用于记录数组中最大的数
int ThisSum = 0;//用于记录当前的连续子数组和
for(int i = 0; i < n; ++i)
{
if(a[i] < 0) //如果无素为负数,则把flag的值加1
++flag;
if(MaxNum < a[i]) //记录数组当前的最大值
MaxNum = a[i];
ThisSum += a[i]; //累加更新当前的子数组之和
if(ThisSum > sum)
{
//若当前连续子数组之和大于记录的子数组之和
//则设置最大连续子数组之和为当前的和
sum = ThisSum;
}
else if(ThisSum < 0)
{
//如果当前连续子数组之和小于0,则抛弃之前的连续子数组,
//从此元素的下一个元素重新计算连续子数组之和
ThisSum = 0;
}
}
//若全是负数,最大值为数组中的最大无素
if(flag == n)
sum = MaxNum;
return sum;
}
我们再来看看测试结果吧,测试代码如下:
int main()
{
int a[100] = {1, -2, 3, 10, -4, 7, 2, -5};
cout<<MaxSum(a,8)<<endl;
return 0;
}
运行结果如下:
从运行结果和测试数据来看,最大的连续子数组应该是3,10,-4,7,2.它们的和就为18.
四、时间复杂度和空间复杂度分析
从代码和上面的解说可以看到,这个算法的时间复杂度只为O(N),而且常数为1,即只需要扫描一次数组即可完成任务。而且用到的辅助空间也非常少,只有四个变量,空间复杂度为O(1)。
五、完整代码代码下载地址:
https://github.com/ljianhui/Arithmetic
文件名:max_sum_of_continuous_sub_array.cpp
分享到:
相关推荐
在线处理法求数列的最大子列和,将时间复杂度降为n,值得学习借鉴
第八次作业 k递增子数列.c
Java 求出数列前20项的和,有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13...求出这个数列的前20项之和。可以得出规律为:后一个数的分母为前一个数分子和分母之和,因此可以得出计算方法如下: for(int i = 1;i;...
百鸡问题 递归与非递归求最大公约数 斐波那契数列递归与非递归算法 递归与非递归求阶乘
斐波那契数列,又称黄金分割数列,斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....这个数列从第三项开始,每一项都等于前两项之和。我上传的是用php中,用递推和迭代求斐波那契数列
【问题描述】编写函数f,功能是用递归的方法求斐波那契数列的第n项,函数原型为 int f(int n),在主函数中输入一个正整数n,调用函数f求出斐波那契数列的第n项,并在主函数中输出。 斐波那契数列:1,1,2,3,5,8,13,...
C语言程序设计-用函数求fibonacci数列前n项的和;说明:fibonacci数列为数列的第一项值为1,第二项值也为1,从第三项开始,每一项均为其前面相邻两项的和;例如:当n=28时,运行结果:832039.c
mpi求调和数列之和。用并行的算法求出调和数列前N项之和
# 题目: # 有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13...求出这个数列的前20项之和。 # 分析: # 请抓住分子与分母的变化规律。
C语言程序设计-求出菲波那契数列的前一项与后一项之比的极限的近似值;例如:当误差为0.0001时,函数值为0.618056;
一个特殊数列与Fibonacci数列的关系,王雅茹,朱福惠,本文在Fibonacci数列的基础上定义了前四项分别是1,4,7,9,并且满足第n项是第n-1 项与第n-3项和第n-4项之和的数列,并通过改变其部分项得到�
EE课程 数列递增子序列 数据与算法 实验报告
2.5等比数列前n项和(一).doc
国防工业大学高数(一)课件。与国防工业大学出的书配套课件。
给定某数字A(1≤A≤9)以及非负整数N(0≤N≤100000),求数列之和S=A+AA+AAA+⋯+AA⋯A(N个A)。例如A=1, N=3时,S=1+11+111=123。 输入格式: 输入数字A与非负整数N。 输出格式: 输出其N项数列之和S的值。 ...
C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++...
等差等比数列中的子数列问题.doc
4、等差数列中不可小视的一个性质 5、递推数列中的不等变形 6、放缩法在数列不等式中的应用 7、高考数列总复习习题集 8、浅谈数列教学中的几个问题 9、求数列通项的两个途径 10、数列解答题的常见题型及解题策略 ...
python斐波那契数列第n项 斐波那契数列是指从0和1开始,后面的每一项都是前面两项的和。即:0、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610……以此类推。这个数列在数学上有着重要的应用,也是...
k阶Fabonacci数列k阶Fabonacci数列k阶Fabonacci数列k阶Fabonacci数列k阶Fabonacci数列k阶Fabonacci数列k阶Fabonacci数列k阶Fabonacci数列k阶Fabonacci数列k阶Fabonacci数列k阶Fabonacci数列k阶Fabonacci数列k阶...