《返回一个整数数组中最大子数组的和》之二

一 实验要求

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

要求: 要求程序必须能处理1000 个元素; 每个元素是int32 类型的;

  输入一个整形数组,数组里有正数也有负数。

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

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

二 设计思想:总体的设计思想在之前一篇中已详细讲过,这里主要添加了对该程序的最大处理数的测试,我主要负责对代码的复审和测试。将程序中数组元素的个数设为宏定义,再通过宏定义对其中的元素个数进行修改。

三 代码:

#include<iostream>
#include<time.h>
#define n 127293
using namespace std;

void main()
{
    int a[n],i,w=0,b[n];


    srand((int)time(0));

    for(i=0;i<n;i++)
        a[i]=-rand()%36+25;

    for(i=0;i<n;i++)
        cout<<a[i]<<endl;

    for(i=0;i<n;i++)
    {
        w+=a[i];
        b[i]=w;
    }

    int t=b[0];

    for(i=0;i<n;i++)
    {
        if(b[i]>t)
            t=b[i];
    }

    
            cout<<"最大子数组的值为:"<<t<<endl;
            
}

 

四 程序运行效果截图:技术分享技术分享技术分享

五 总结

通过这次合作我发现,合作确实能够提高工作与学习效率,确实能开阔思路与眼界。让我更加体会合作的好处。

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。