一、题目要求
题目:返回一个整数数组中最大子数组的和。
要求：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
数组要足够大，直到溢出。
溢出之后，加判断。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
二、设计思想
由于溢出会在最后一次不溢出的结果上加一位，导致寄存器内存不过放置进位导致的溢出，故判断要加在这一次加法的前面。
三、源代码
#include <iostream.h>
long int MaxSum2(long int *A, int n)
{
long int nStart = A[n-1];
long float nAll = A[n-1];
for(int i = n-2;i>=0;--i)
{
if(nStart<0)
nStart = 0;
nStart += A[i];
if(nStart>=nAll)
{
nAll = nStart;
if(nAll>=1073741824)
cout<<"溢出!"<<" ";
}
}
return nAll;
}
int main(void)
{
long int qian[100020];
for(int i=0;i<100020;i++)
{
qian[i]=i;
cout<<qian[i]<<" ";
}
cout<<MaxSum2(qian,100020)<<endl;
return 0;
}
四、结果截图
五、心得体会
内存溢出是一个很严重的问题，不能忽视，然而在平时的编程过程中我们很少回去考虑这个问题。但是是在银行等数据量庞大的地方，是特别值得注意。然而增加溢出判读，不能从根本上解决问题。要根本上解决问题，一要扩大范围，int32改为更大的，如果超过了最大的范围，就要自定义加法函数，来算更大的数。这样才能从根本上解决这样的问题。在刚看到这个问题时我们也着实为难了一阵不知道该做些什么才能解决问题。后来在老师的指引下算是找到了解决的办法。