返回一个整数数组中最大子数组的和-课堂训练(子数组为连续)

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

设计思路：

用随机数产生N个随机数放入一个数组里面，找到所有的子数组，并求和取最大的那个数组输出。

代码：

#include<iostream>
#include<ctime>
#define N 5

using namespace std;

void main()
{
    srand(unsigned(time(NULL)));      
    //用于正负号产生
    int t;       
    //存放随机数
    int A[N];
    int B[N][N];   //存数组和
    int i,j,k;
    int sum;

    for(i=0;i<N;i++)
    {
        t=rand()%2;
        if(t==0)
            A[i]=rand();
        else
            A[i]=-rand();
        cout<<A[i]<<"\t";
    }

    cout<<endl;
    for(i=0;i<N;i++)
    {
        for(j=0;j<N-i;j++)
        {
            sum=0;
            for(k=j;k<=j+i;k++)
            {
                sum=sum+A[k];
                B[i][j]=sum;
            }
        }
    }
    /*
    for(i=0;i<N;i++)
    {
        for(j=0;j<N-i;j++)
            cout<<B[i][j]<<"\t";
        cout<<endl;
    }
    */

    //求最大字数组的位数
    int max=A[0];
    int x,y;
    for(i=0;i<N;i++)
    {
        for(j=0;j<N-i;j++)
        {
            if(max<B[i][j])
            {
                max=B[i][j];
                x=i;
                y=j;
            }
        }
    }
    cout<<"最大子数组之和为:"<<max<<endl;
    cout<<"最大子数组为:";
    for(i=0,j=y;i<=x;i++,j++)
        cout<<A[j]<<"\t";
}

技术分享

总结：设计思路方面没有实现要求的时间复杂度O(n),编程代码还是书写不规范仍需改善。

总结表：

周活动总结表

日期任务	听课	编写程序	上网查询资料	日总计
周日		120	30	150
周五	110		20	130
周六			20	20

具体总结表

日期	开始时间	结束时间	中断时间	净时间	活动	备注
3/20	10:00	12:00	10	110	上课	软件工程概论
3/20	20:00	20:20		20	上网	查询资料
3/21	15:00	15:20		20	上网	查询资料
3/22	14:00	16:20	20	120	编程	作业
3/22	13:00	13:30		30	上网	查询资料

缺陷总结表

日期	编号	类型	进入阶段	排除阶段	修复时间
3/20	1	少括号	编程	编译	lmin
	2	未定义初始数值	编程	编译	lmin
	3	时间复杂度	设计	编译	（未完善没做到O（n））