帮我看看做的对不？散100分.........................
//m个整数组成的整数序列中连续n个整数和的最大值(n<=m)
//example: -1,2,3,4,-2的最大值是2+3+4 = 9
//程序中a[0]是数组的大小
#include <iostream>
using namespace std;
int max(int *a);
int main()
{
int a[]={5,-1,2,3,4,-2};
cout<<max(a)<<endl;
cin.get();
return 0;
}
int max(int *a)
{
int low=1,max=a[1],max_sum=0,sum=0;
while(low<=a[0])
{
if(a[low]>max)
max=a[low];
sum+=a[low++];
if(sum>max_sum)
max_sum=sum;
if(sum<0)
sum=0;
}
if(max<0)
return max;
else
return max_sum;
}
请使劲的批评啊...............
问题点数：100、回复次数：44Top
1 楼zyp2kyear（E腾鸟）回复于 2004-12-02 13:55:25 得分 0
UP,看的晕晕Top
2 楼Lonelywolf1899（プログラマ）回复于 2004-12-02 13:59:21 得分 0
参数只有 int * a，m和n那两个参数呢？
这代码，不能卖钱Top
3 楼MCR（）回复于 2004-12-02 14:11:16 得分 0
cin.get(); // 这句何用？Top
4 楼wwxsoft（婉儿）回复于 2004-12-02 14:18:50 得分 10
haha结果正确就行了
Top
5 楼judeyouzhi（游鱼）回复于 2004-12-02 14:24:28 得分 20
从前往后扫描正数和0就往上加，遇到负数保存当前结果，保存时比较前一次记录，大则代替，小则不改变。是这样的过程吗？Top
6 楼Michael_555（Nothing）回复于 2004-12-02 14:30:17 得分 0
但是如果整个数组内全是负数呢？Top
7 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 14:35:02 得分 0
Lonelywolf1899(私は君のことが好きです)
n是不定的，要什么输入啊？
请把我程序的毛病告诉我，可以吗？我是真心请教的。
还有，不卖钱的，小妹就是学着玩的，不是什么程序员 ^_^Top
8 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 14:36:52 得分 0
MCR()
cin.get(); // 这句何用？
无用，只是编译器输出的问题，有时候不加它，看不到结果。Top
9 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 14:39:05 得分 0
Michael_555(Stack)
但是如果整个数组内全是负数呢？
max在程序中保存数组中的最大值，
在返回的时候判断，当max<0的时候，返回最大的负数。Top
10 楼kobefly（科比--网络学习中）回复于 2004-12-02 14:51:37 得分 0
int max(int *a)
{
int result = 0;
int temp;
int index = 1;
while(index < a[0])
{
temp = 0;
while(a[index] >= 0 && index <= a[0])
{
temp += a[index];
index++;
}
index++;
if(temp > result)
result = temp;
}
return result;
}
上边是我写的一个max函数
你的函数存在问题
比如a[] = {5,-1,2,3,-1,7}
这样的数组就不能得出正确结果
Top
11 楼xuelong_zl（点雨点[我身上咋就没MM的香水味涅??#-_-]）回复于 2004-12-02 14:55:56 得分 0
程序的思想很厉害,不过我认为最好将程序改为由用户自行输入数据会更好一些,我想这些改动对于你这个高手来讲应该没什么吧!
Top
12 楼Michael_555（Nothing）回复于 2004-12-02 14:57:34 得分 0
260005065(懒在床上不起)
n是不定的，要什么输入啊？
请把我程序的毛病告诉我，可以吗？我是真心请教的。
reply:
int main()
{
int *a = NULL;
int n,i;
cout<<"Input the total number:";
cin>>n;
a = new int[(n+1)];
a[0] = n;
for(i=1;i<n+1;i++)
{
cin>>a[i];
}
cout<<max(a)<<endl;
if(a!=NULL)
{
delete(a);
a = NULL;
}
while(cin.get()!='Q');//intput Q to exit
return 0;
}
Top
13 楼sutra（一生一世与C相约）回复于 2004-12-02 14:58:11 得分 0
C版的递归实现，递归仅执行COUNT次，COUNT为数列长度。
#define COUNT 5
int max( int *N, int n, int *m )
//m为最大和的地址，使用前由用户自己初使化。
{
int r, t ;
r = n == 1 || ( t = max(N+1, n-1, m ) ) <= 0 ? *N : *N + t ;
return r > *m ? *m=r : r ;
}
int main()
{
int m = 0, A[COUNT]={-1,2,3,4,-2};
max( A, COUNT, &m ) ;
printf( "Result:%d\n", m ) ;
return 0;
}Top
14 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 14:59:06 得分 0
kobefly(科比---不惧挑战!)
有结果啊，结果是 11 啊？？？正确啊。。
您的函数结果是5，是错的 ^_^Top
15 楼Michael_555（Nothing）回复于 2004-12-02 15:00:07 得分 0
260005065 (懒在床上不起) ,
你的算法得出来的结果是把数组中所有的整数加起来，而不是连续n个整数和的最大值Top
16 楼xuelong_zl（点雨点[我身上咋就没MM的香水味涅??#-_-]）回复于 2004-12-02 15:09:08 得分 0
Michael_555(Stack) 我想你可以想想这段代码的作用
if(sum<0)
sum=0;Top
17 楼iiml（哦，我明白了）回复于 2004-12-02 15:12:38 得分 0
全是负数是不对Top
18 楼zengwujun（月之海 为linux入门奋斗100天）回复于 2004-12-02 15:13:14 得分 0
借用MM的积分，看看我的算法吧，谢谢！
#include <iostream>
using namespace std;
int max(int *a,int n);
int main()
{
int a[] = {10,7,6,-1,6,8,-5,0,9,9,-3};
cout<<max(a,3)<<endl;//计算3个连续整数吧
//cin.get();
return 0;
}
int max(int *a,int n)
{
int iMax = 0;
int iAdd = 0;//当前计算值相对于iMax的增量
for(int I=1;I<=n;I++)
iMax += a[I];
for(;I<=a[0];I++)
{
iAdd += a[I] - a[I-n];
if(iAdd>0)
{
iMax +=iAdd;
iAdd = 0;
}
}
return iMax;
}
Top
19 楼zengwujun（月之海 为linux入门奋斗100天）回复于 2004-12-02 15:15:11 得分 0
晕，粘贴过来的，没给我排版啊Top
20 楼iiml（哦，我明白了）回复于 2004-12-02 15:16:02 得分 0
不好意思，看错了，程序是正确的Top
21 楼zengwujun（月之海 为linux入门奋斗100天）回复于 2004-12-02 15:18:57 得分 0
递归函数不可取，时间复杂度太大，我的算法是最简单的，O(n)搞定，我要分！Top
22 楼zyk7069（坚强的C++！还没倒？我就学）回复于 2004-12-02 15:25:58 得分 0
看着你这个程序我感到头晕，你第一个数要等于max干什么呀？你这是找出最大数！
int fun(int *a,int m,int n)
{
int max=0,sum=0;
for(int i=0;i<m;i++)
{
if((m-i)<n)
break;
for(int j=i;j<n;j++)
sum += a[j];
if(sum>max)
max = sum;
}
cout << "max = " << max;
}Top
23 楼zyk7069（坚强的C++！还没倒？我就学）回复于 2004-12-02 15:32:56 得分 0
to:Michael_555(Stack)
你的程序有点问题，你既然用delete释放了内存，那么a在你释放以后不能在使用了，即使是a=NULL。Top
24 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 15:34:46 得分 0
xuelong_zl(磊)
程序的思想很厉害,不过我认为最好将程序改为由用户自行输入数据会更好一些,我想这些改动对于你这个高手来讲应该没什么吧!
呵呵，小妹不是高手，才学编程玩的。
另外让您看的是函数max ^_^Top
25 楼xuelong_zl（点雨点[我身上咋就没MM的香水味涅??#-_-]）回复于 2004-12-02 15:53:02 得分 0
我想问一下楼主,你是不是因为算法复杂度的原因,也这么做的?不然是穷举会更方便一些吧
另外根据题意n应该为一个定值,你认为呢?Top
26 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 16:01:41 得分 0
高手，虽然时间复杂度太太...........高了，不符合要求，但是写的真好。
50 分。Top
27 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 16:02:34 得分 0
Michael_555(Stack)
260005065 (懒在床上不起) ,
你的算法得出来的结果是把数组中所有的整数加起来，而不是连续n个整数和的最大值
你在好好看看吧！！
^_^Top
28 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 16:04:15 得分 0
50分 给sutra(经典答案 /*短最美 小最优*/) 了，
还有50 ^_^Top
29 楼kobefly（科比--网络学习中）回复于 2004-12-02 16:22:31 得分 0
int max(int *a)
{
int result = 0;
int temp;
int index = 1;
while(index <= a[0]) //不好意思,刚才这里少了个=
{
temp = 0;
while(a[index] >= 0 && index <= a[0])
{
temp += a[index];
index++;
}
index++;
if(temp > result)
result = temp;
}
return result;
}
楼主的程序跟自己说的要求不配套
我举的例子
结果应该是7
而你的程序11 == 2+3-1+7?
你自己再思考一下吧
Top
30 楼freeskypx（吸血鬼伯爵）回复于 2004-12-02 16:26:01 得分 20
cin.get();
return 0;
这两句常常组合在一起用，用来接收一个键返回空键
也就是说，程序运行到这里就打住不动了，等你按回一个键后就返回了，结束程序了Top
31 楼Michael_555（Nothing）回复于 2004-12-02 16:26:56 得分 0
260005065 (懒在床上不起) ，你的算法确实有问题啊。
例如输入数组：6,-1,3,4,-2
得出的结果将是12，而不是7。
if(sum<0)
sum=0;
这儿错了，因为如果数组开始时正数的话，sum要与后面的负数累加致小于零才会清零。
a[]={6,-1,3,4,-2}运行的过程如下：
max sum max_sum
第一次循环： 6 6 6
2 ： 6 5 6
3 ： 6 8 8
4 ： 6 12 12
5 ： 6 10 12
int max(int *a)
{
int low=1,max=a[1],max_sum=0,sum=0;
while(low<=a[0])
{
if(a[low]>max)
max=a[low];
sum+=a[low++];
if(sum>max_sum)
max_sum=sum;
if(sum<0)
sum=0;
}
if(max<0)
return max;
else
return max_sum;
}
Top
32 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 16:34:20 得分 0
to Michael_555(Stack)
例如输入数组：6,-1,3,4,-2
得出的结果将是12，而不是7。
答案就是12 啊，不是7啊。
6 + -1 + 3 + 4 = 12
12>7
要最大的，当然不是7了。
^_^Top
33 楼kobefly（科比--网络学习中）回复于 2004-12-02 16:42:13 得分 0
to Michael_555(Stack)
例如输入数组：6,-1,3,4,-2
得出的结果将是12，而不是7。
答案就是12 啊，不是7啊。
6 + -1 + 3 + 4 = 12
12>7
要最大的，当然不是7了。
^_^
越来越糊涂
不知道楼主要做什么东东?Top
34 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 16:43:06 得分 0
to kobefly(科比---不惧挑战!)
m个整数组成的整数序列中连续n个整数和的最大值(n<=m)
看好了，求的是最大值，该最大值是连续的n个数的和，条件是(n<=m)...............
-1, 2, 3, -1, 7 的连续数的和最大是 2 + 3 + -1 + 7 = 11 ，怎么错了，
它不连续？它不最大？
您在好好看看吧 ^_^Top
35 楼Michael_555（Nothing）回复于 2004-12-02 16:46:25 得分 0
不好意思，我弄错了，我看成了连续n个正整数和的最大值
//m个整数组成的整数序列中连续n个整数和的最大值(n<=m)
//example: -1,2,3,4,-2的最大值是2+3+4 = 9
//程序中a[0]是数组的大小
Top
36 楼sutra（一生一世与C相约）回复于 2004-12-02 16:48:44 得分 50
时间复杂度也不大啊，才O（N），下面是它的非递归版，计算原理是相同的。
#define COUNT 5
int max( int *N, int n )
{
int i, m, r ;
//当N的首元素表示数列长度时取消n参数，此处加上: int n ; n=*N++ ;
for( i = r =m = 0 ; i < n ; ++i, ++N ) {
r = *N + (r <= 0 ? 0 : r) ;
if( r > m ) m = r ;
}
return m ;
}
int main()
{
int m = 0, A[COUNT]={-1,2,3,4,-2};
m = max( A, COUNT ) ;
printf( "Result:%d\n", m ) ;
return 0;
}
Top
37 楼kobefly（科比--网络学习中）回复于 2004-12-02 16:53:57 得分 0
看好了，求的是最大值，该最大值是连续的n个数的和，条件是(n<=m)...............
哦
明白了
不是连续正数
我错了
惭愧Top
38 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 17:09:28 得分 0
to sutra(经典答案 /*短最美 小最优*/)
的程序和我的其实一样，一个是for，一个是while。
只是没考虑都是负数的情况。
递归每次都要保存数据的，耽误效率。Top
39 楼qufan（打死不回头）回复于 2004-12-02 17:20:39 得分 0
我好郁闷阿
开始看到连续两个字就想到要用深度搜索了
ft，居然是下标连续，我读书少没办法哦
不过楼主的算法真让我等大吃一斤
你的max写的的确有问题
如果是一个死的模块你还不如就让他包括在main中呢？？
还有你要函数实现的功能比你要求得多哦
另外你认为很好的 sutra(经典答案 /*短最美 小最优*/) 兄弟的算法呵呵
有句话说：你应该让事情变得简单但不要太简单哦
谁都知道递归的消耗是多大，而
int max( int *N, int n, int *m )
//m为最大和的地址，使用前由用户自己初使化。
{
int r, t ;
r = n == 1 || ( t = max(N+1, n-1, m ) ) <= 0 ? *N : *N + t ;
return r > *m ? *m=r : r ;
}
这个程序分析很难哦 ，看了半天得画图才行哦
不过，要找最大的必先扫描数组，然后记下最大的数和所在地址，然后一路加过去
上面的算法直觉上 我觉得有问题哈Top
40 楼beyondtkl（大龙驹<*好久没来了,兄弟们好吧。*>）回复于 2004-12-02 17:26:08 得分 0
MKTop
41 楼Anderslijp（一剑飘飘）回复于 2004-12-02 17:39:32 得分 0
#include <iostream>
#include <stdlib.h>
int sum( int a[],int num)
{
static int maxsum = a[1];
if(num > a[0])
{
return maxsum;
}
int tempmax = 0;
int j = 0;
for ( int i = 1; i <= a[0] - num + 1; i++)
{
j = i;
for( ;j < num+i;j++)
{
tempmax = tempmax + a[j];
}
if(tempmax > maxsum)
{
maxsum = tempmax;
}
tempmax = 0;
}
sum( a, num+1);
}
int main()
{
int a[] = {5,6,-1,3,4,-2};
int b = sum(a,1);
cout << b << endl;
system( "pause" );
return 0;
}Top
42 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 17:56:45 得分 0
to qufan(打死不回头)
不过，要找最大的必先扫描数组，然后记下最大的数和所在地址，然后一路加过去
这想法不应该是对的，比如-100，-20，30，，，1000，1000，1000，，，，-1999，2000
当2000是数组中最大数，省略的地方都是负数，那么结果就是3000，首先找不找2000，是没用的。
另外我认为sutra(经典答案 /*短最美 小最优*/) 兄弟的算法想法很好啊很巧妙。
对于max有问题：
是的，它可以没有，但是对于数组全是负数怎么办？
我们怎么在一次遍历数组，就知道它全是负数？
帮我解决一下这两个问题。
^_^Top
43 楼xuelong_zl（点雨点[我身上咋就没MM的香水味涅??#-_-]）回复于 2004-12-02 18:23:46 得分 0
To 260005065(懒在床上不起)
我想这个方法可以一次遍历数组，就知道它全是负数？
#include "stdio.h"
#define n 4
main()
{ int i;
int j=0;
static int a[n]={-1,-2,-3,-4};
for (i=0;i<4;i++)
{ if (a[i]<0)
j++;
else
j--;
printf("j=%d\n",j);
if (j==n)
printf("all -value\n");
}
}Top
44 楼260005065（宁独遗与世，亦当皓首穷经，但有所得，无悔无怨。）回复于 2004-12-02 20:55:20 得分 0
结帐Top
