要求:
1.要求程序必须能处理1000 个元素;
2.每个元素是int32 类型的,出现子数组之和大于整型表示的最大范围会出现什么情况;
3.输入一个整形数组,数组里有正数也有负数。
4.数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
5.求所有子数组的和的最大值。要求时间复杂度为O(n)。
实现代码:
#include "stdafx.h"
#include "stdlib.h"
int a[1000] = { 0 };
int _tmain(int argc, _TCHAR* argv[]) { int a[1000] = { 0 };
for (int i = 0; i < 1000; i++)
{
a[i] = rand() % 10000 - 5000;
}
for (int j = 0; j < 999; j++)
{
printf("%d ", a[j]);
}
//计算连续最大子数组
//计算连续最大子数组
int maxsum = 0;
int nowsum = 0;
int x;
for (int k = 0; k <1000; k++)
{
nowsum += a[k];
x = nowsum;
if (a[k +1] > 2147483647 - x)
{
printf("超出范围");
maxsum = maxsum + a[k + 1];
printf("%d", k+1);
break;
}
else
{
if (nowsum > maxsum)
{
maxsum = nowsum;
}
else if (nowsum < 0)
{
nowsum = 0;
}
}
}
printf("
结果是
"); printf("%d
", maxsum);
return 0;
return 0;
}
如果随机生成的的数字长度超过int类型的最大值,会显示“常量太大”。
if (a[k +1] > 2147483647 - x)
{
printf("超出范围");
maxsum = maxsum + a[k + 1];
printf("%d", k+1);
break;
},此语句判断数字的大小,如果超出,输出“超出范围”,并计算之前的最大子数组的和。
最终显示数据超出之前最大子数组的和。
最后附上两个人一起编程时的照片: