Chinaunix首页 | 论坛 | 博客
  • 博客访问: 458093
  • 博文数量: 72
  • 博客积分: 1851
  • 博客等级: 上尉
  • 技术积分: 1464
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-16 17:50
文章分类

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: C/C++

2010-09-25 23:32:10

最近看到论坛上出现一道题目,求连续元素的和最大,觉得有些意思就来写写自己的解法。
我的解法就是一个一个的求,采用公式: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


如果有错误,请您留言,谢谢!
阅读(1258) | 评论(0) | 转发(0) |
0

上一篇:多项式乘积

下一篇:组合算法

给主人留下些什么吧!~~