寻找一组数组中最大的一组子数组

时间：2014-03-11 00:34:19 收藏：0 阅读：429

组员

赵天20113007

李金吉20113008

算法分析：

（1）这个问题最基本的解决办法就是找出各个子数组的加和，然后进行排序，为了更清晰地理解，假定一个数组arr[]={8,9,10,-1,20,-30,4}

再设一个数组 a[100]来存储子数组相加之和，则：

a[0]=arr[0];

a[1]=arr[0]+arr[1];

a[2]=arr[0]+arr[1]+arr[2];

a[3]=arr[0]+arr[1]+arr[2]+a[3];

....

a[7]=arr[1];

a[8]=arr[1]+arr[2];

a[9]=arr[1]+arr[2]+arr[3];

....

我们将给定数组的某一单元确定化，然后用此单元与数组中其他直接相邻或间接相邻的单元相加，直至把包括此单元的所有子数组之和加完，然后在确定另一个单元，继续相加....

这种算法要用两个for循环，时间复杂度为n*n。

(2)我么要进行异常处理，例如当数组为空时程序也应该能运行，输出提示错误的信息。

(3)我们要对程序进行单元测试，在某些极端的情况下也能运行，例如arr3[]={0}，数组为空等.

以下是程序代码及运行结果：

#include<iostream>
#define null -858993460
using 
namespace std;
 
 
void main()
{
    int 
arr[]={8,9,10,-1,20,-30,4};
    int 
arr2[]={-9,-1,-4,-123};
    int 
arr3[]={0};
    int 
arr4[]={7,9,8};
    int 
arr5[3];
 
    int 
test(int 
list[],int 
length);
 
    cout<<test(arr,7)<<endl;
    cout<<test(arr2,4)<<endl;
    cout<<test(arr3,1)<<endl;
    cout<<test(arr4,3)<<endl;
    cout<<test(arr5,0)<<endl;
     
 
 
}
int 
test(int 
list[],int 
length)
{
    int 
a[100]={0},x=0;
    int 
max;
    int 
i,j;
    int 
k=0;
 
    if(list==NULL||length==0)
    {
        cout<<"error!inter is null!";
        return 
0;
    }
     
     
    for(i=0;i<length;i++)
    {
        a[k]=list[i];
        for(j=i;j<length;j++)
        {
            a[k+1]=a[k]+list[j+1];
            k++;
        }
    }
    max=a[0];
    for(i=0;i<k;i++)
    {
        if(max<a[i])
        {
            max=a[i];
        }
         
    }
    return 
max;
     
 
}

运行结果：

bubuko.com,布布扣

附结对讨论图片：

bubuko.com,布布扣

寻找一组数组中最大的一组子数组,布布扣,bubuko.com

原文：http://www.cnblogs.com/lijinji/p/3592506.html