软工随堂练 找出和值最小的子数组 尹亚男 赵静娜

#include <iostream.h>
void main()
{
    int a[10]={-3,-1,-1,0,-1,5,4,-1,3,-1},sum[10][10];
    //sum[i][j]存储在第i+1和第j+1个数之间的数构成的子数组的和值
    int max=a[0];//和值最大值
    int i,j,k,m=1,n=1;
//    cout<<"十个整数："<<endl;
//    for(i=0;i<10;i++) cin>>a[i];
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
            sum[i][j]=0;//初始化
    for(i=0;i<10;i++)
    {
        for(j=i+1;j<10;j++)
        {
            for(k=i;k<=j;k++)
                sum[i][j]+=a[k];//求子数组和值
        }
        sum[i][i]=a[i];
    }
    for(i=0;i<10;i++)
    {
        for(j=0;j<10;j++)
        {
            cout<<sum[i][j]<<"	";
        }
    }
    for(i=0;i<10;i++)//比较法找出最大值
    {
        for(j=i;j<10;j++)
        {
            if(sum[i][j]>max) 
            {
                max=sum[i][j];m=i+1;n=j+1;    
            }
        }            
    }
    if(m==n) cout<<"最大值是第"<<m<<"个数构成的子数组"<<endl;
    else cout<<"子数组和值最大的是第"<<m<<"个数到第"<<n<<"个数之间的子数组"<<endl;
    cout<<"最大值是："<<max<<endl;
}

题目要求时间复杂度O（n），没有想到可行办法。

以上代码是经过探讨后选择的方案，将所有子数组枚举求和存储在sum[][]中，再对其求最大值。为了测试方便输出了sum[][]以及子数组的定位。

测试了几组数据，正、负、零都没有错误。（这里忽略故意输入非int型情况）