返回一个整数数组中最大子数组的和 C语言

1、题目:返回一个整数数组中最大子数组的和。
2、要求：
　　要求程序必须能处理1000 个元素；
　　每个元素是int32 类型的；
　　输入一个整形数组，数组里有正数也有负数。
　　数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
　　求所有子数组的和的最大值。要求时间复杂度为O(n)。
3、设计思路：
　　将数组大小定义为1000，对于每个元素定义为int32类型，将求和函数设置为int 类型，这样可以方便观测数据的溢出，让数组元素可以超出范围。
4.程序代码：
#include<iostream>
#include<time.h>
#include<conio.h>
#define N 1000
using namespace std;
void RandIn(int IntNum,int A[])   //随机生成数组
{
    cout<<“整数内容”<<endl;
    for(int i=0;i<IntNum;i++)
    {
        A[i]=rand()-rand();
        cout<<A[i]; 
        if(i%15==4)
            cout<<endl;
        else
            cout<<‘\t’;
    }
}
void SelMax(int IntNum,int A[],auto &sum)
{
    int buffer=0;
    int count1=0;        //求和的数值个数
    int count2=0;    //进行的运算次数
    for(int j=0;j<=IntNum;j++)
    {
        if(j==IntNum)
        {
            j=0;
        }
        buffer+=A[j];
        count1++;
        count2++;
        if(buffer<0)   
        {
            buffer=0;
            count1=0;
        }
        if(sum<buffer)//sum始终记录下存在的最大和
        {
            sum=buffer;
        }
       
        {
            break;
        }
    }
}
void main()
{
    
    int IntNum;
    int A[N];
    int q=0;
    while(q==0)
    {
        auto sum=0;
        srand((unsigned)time(NULL));
        cout<<“请输入数组元素的个数:”;
        cin>>IntNum;
        RandIn(IntNum,A);
        SelMax(IntNum,A,sum);
        cout<<endl;
        cout<<sum<<endl;
        cout<<“是否继续测试(输入0则继续否则停止)”;
        cin>>q;
        system(“cls”);
    }
}
5.运行结果
     无溢出时：
     
         溢出时：对代码进行改动，在求和代码中*4294967296   这样在运行程序之后就会溢出，截图如下：
 

6.实验感想：这次实验让我明白了实验代码简练的重要性，算法优化的重要性，这样可以节省运算时间，所以这次试验我收获很多，下次

实验我会更加用心，学习到更多知识，让我更上一层楼。

7.小组相片：

 

 

posted on 2018-10-14 15:13 孤独的漂泊# 阅读(…) 评论(…) 编辑 收藏

版权声明：本文为sunyangkai原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/sunyangkai/p/9786425.html