给定一个整数数组(有正数有负数),找出总和最大的连续数列,并返回总和。

原创
2016/11/26 09:58
阅读数 3.6K

一、什么是求最大连续子数列和

首先来看看这是个怎样的问题的,问题描述:一个整型数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和,求所有子数组的和的最大值。注意:当全是负数的情况时,返回最大的那个负数

 

二、解题思路

这个问题的思路其实非常简单,从左到右扫描数组,在扫描过程中,记录数组的负数的个数和扫描过中数据中的最大值,并累加每个扫描到的数据的和,假设用变量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,而与现实有点不一样,所以就要记录负数的数量,当负数的数量等于元素的个数(即全是负数)时,就要把最大连续子序列和置为最大的负数。这也是前面所说的,在扫描过程中记录负数的个数和最大元素的作用。

 

三、实现代码

 

[cpp] view plain copy

print?

  1. int MaxSum(int* a,int n)  
  2. {  
  3.     int sum = 0; //用于记录最大的连续子数组和  
  4.     int flag = 0;//用于记录负数的个数  
  5.     int MaxNum = *a;//用于记录数组中最大的数  
  6.     int ThisSum = 0;//用于记录当前的连续子数组和  
  7.     for(int i = 0; i < n; ++i)  
  8.     {  
  9.         if(a[i] < 0) //如果无素为负数,则把flag的值加1  
  10.             ++flag;  
  11.         if(MaxNum < a[i]) //记录数组当前的最大值  
  12.             MaxNum = a[i];  
  13.         ThisSum += a[i]; //累加更新当前的子数组之和  
  14.         if(ThisSum > sum)  
  15.         {  
  16.             //若当前连续子数组之和大于记录的子数组之和  
  17.             //则设置最大连续子数组之和为当前的和  
  18.             sum = ThisSum;  
  19.         }  
  20.         else if(ThisSum < 0)  
  21.         {  
  22.             //如果当前连续子数组之和小于0,则抛弃之前的连续子数组,  
  23.             //从此元素的下一个元素重新计算连续子数组之和  
  24.             ThisSum = 0;  
  25.         }  
  26.     }  
  27.     //若全是负数,最大值为数组中的最大无素  
  28.     if(flag == n)  
  29.         sum = MaxNum;  
  30.     return sum;  
  31. }  

我们再来看看测试结果吧,测试代码如下:

 

 

[cpp] view plain copy

print?

  1. int main()  
  2. {  
  3.     int a[100] = {1, -2, 3, 10, -4, 7, 2, -5};  
  4.     cout<<MaxSum(a,8)<<endl;  
  5.     return 0;  
  6. }  

运行结果如下:

 

从运行结果和测试数据来看,最大的连续子数组应该是3,10,-4,7,2.它们的和就为18.

 

四、时间复杂度和空间复杂度分析

从代码和上面的解说可以看到,这个算法的时间复杂度只为O(N),而且常数为1,即只需要扫描一次数组即可完成任务。而且用到的辅助空间也非常少,只有四个变量,空间复杂度为O(1)。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部