求连续元素和最大

时间：2010-09-25 来源：datao0907

最近看到论坛上出现一道题目，求连续元素的和最大，觉得有些意思就来写写自己的解法。
我的解法就是一个一个的求，采用公式:sum[i][j+1]=sum[i][j]+a[i+j+1]，其中sum[i][j+1]的含义是：从第i个元素开始，长度为j+1个元素的和，再在sum数组中找出元素最大的那个，记录下和，开始序号，长度。
代码如下:

#include <iostream>
using namespace std;
//求连续元素和的最大

template<class T>
void max_sum(const T *a,int size){
T sum[size][size];
T max=0;
int index,len;
for(int i=0;i<size;++i){
for(int j=0;j<size;++j)
sum[i][j]=0;
sum[i][1]=a[i];
}
for(int i=0;i<size;++i)
{
for(int j=1;j<size&&((i+j)<size);++j)

// if(sum[i][j+1]<(sum[i][j]+a[i+j-1]))这行如果加上就错误了

{
sum[i][j]=sum[i][j-1]+a[i+j-1];
cout<<"sum["<<i<<"]["<<j<<"]:"<<sum[i][j]<<endl;
if(max<sum[i][j])
{
index=i;len=j;
max=sum[i][j];
}
}
}
cout<<"起始元素a["<<index<<"]:"<<a[index]<<" 最大长度:"<<len<<" 最大元素值:"<<sum[index][len]
<<endl;
}

int main(){
int a[]={9,-12,120,8,-20,100,30,-89,20};
max_sum(a,9);
return 0;
}

编译后执行如下:

./a.out
sum[0][1]:9
sum[0][2]:-3
sum[0][3]:117
sum[0][4]:125
sum[0][5]:105
sum[0][6]:205
sum[0][7]:235
sum[0][8]:146
sum[1][1]:-12
sum[1][2]:108
sum[1][3]:116
sum[1][4]:96
sum[1][5]:196
sum[1][6]:226
sum[1][7]:137
sum[2][1]:120
sum[2][2]:128
sum[2][3]:108
sum[2][4]:208
sum[2][5]:238
sum[2][6]:149
sum[3][1]:8
sum[3][2]:-12
sum[3][3]:88
sum[3][4]:118
sum[3][5]:29
sum[4][1]:-20
sum[4][2]:80
sum[4][3]:110
sum[4][4]:21
sum[5][1]:100
sum[5][2]:130
sum[5][3]:41
sum[6][1]:30
sum[6][2]:-59
sum[7][1]:-89
起始元素a[2]:120 最大长度:5 最大元素值:2