求最大子数组的程序设计

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

一、设计思路：通过输入数组的长度和数组中数的取值范围，产生一个随机数组，并用随机数决定正负号。然后在一次循环中，将数组中的数依次相加，若相加大于0则继续相加，若相加小于0则舍弃之前的数，重新开始相加，并且在循环中记录相加产生的最大的数，即为最大子数组的和。

二、代码：

#include<iostream>
using namespace std;

void main()
{
    int i,x,y,z;
    int s,sum,head,end,h,e;
    cout<<"请输入数组的长度：";
    cin>>x;
    cout<<"请输入数组的取值范围:";
    cin>>z;
    int *a=new int[x];

    for(i=0;i<x;i++)
    {
        a[i]=rand()%z;
        y=rand()%2;
        if(y==0)
        {
            a[i]=-a[i];
        }
    }
      
    for(i=0;i<x;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;

    sum=0;
    s=0;
    e=0;
    h=0;

    for(i=0;i<x;i++)
    {
        s+=a[i];
        if(s>0)
        {
            e++;
        }
        else
        {
            s=0;
            h=i+1;
            e++;
        }
        if(s>sum)
        {
            sum=s;
            head=h;
            end=e;
        }
    }
    cout<<"最大子数组的和为："<<sum<<endl;
    cout<<"最大子数组为：";
    for(i=head;i<end;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;

    delete a;

}