软件工程结对开发之求一维数组中连续最大子数组之和2

浏览数：21 / 时间：2015年06月08日

一、题目要求

题目:返回一个整数数组中最大子数组的和。

要求：

要求程序必须能处理1000 个元素；

每个元素是int32 类型的；

输入一个整形数组，数组里有正数也有负数；

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和；

求所有子数组的和的最大值。要求时间复杂度为O(n)；

结果溢出之后能判断。

二、设计思想

在求最大连续子数组时同样用动态法，对于新增的要求，可以增大随机产生数的倍数，如果结果溢出则输出溢出提示字样，其中int类型rand（）随机产生数范围是0~32767，int32最大数是2147360000。

三、代码

#include<iostream.h>
#include<stdlib.h>
#include<time.h>
void main()
{
    while(1)
    {
        int length,temp;
        int *arr=new int[length];
        cout<<"请输入该数组长度:";
        cin>>length;
        //cout<<"请输入该数组:";
        srand((unsigned)time(NULL));
        for(int i=0;i<length;i++)
        {
            arr[i]=rand()*10000;
            temp=rand()%2;
            if(temp==0)
            {
                arr[i]=arr[i];
            }
            else
            {
                arr[i]=-arr[i];
            }
            cout<<arr[i]<<"\t";
        }
        int result = arr[0];
        int sum = arr[0];
        for(i=1;i<length;i++)
        {
            if (sum > 0)
            {
                sum += arr[i];
            }
            else
            {
                sum =arr[i];
            }
            if (sum >result)
                result = sum;
        }
        if(result<2147360000||result==2147360000)
        {
            cout<<"该数组中最大连续子数组之和是:"<<result<<endl;
        }
        else
        {
            cout<<"超出最大范围溢出!"<<endl;
        }
        cout<<"----------------------------------------"<<endl;
    }
}