|
|
#2
寒风中的细雨2011-02-26 10:00
程序代码:/* *x1 -x2 x3 -x4(xi全为正数) *判断 x3是否要加入 到{x1, -x2, x3}序列中的标准为 x2<=x3成立 *否则 不加入 就表示 序列在-x2此处断开 */ #include <stdio.h> #include <math.h> #define MAX_SIZE 10000 struct node { int sum;//存放最大和 int first_site;//存放第一个元数的下标值 int end_site;//存放最后一个元数的下标值 }; int main() { int num;//存放待要输入整数的个数 int a[MAX_SIZE];//存放输入整数 的数组 int i = 0; int temp = 0; struct node num_1, num_2; while( scanf("%d", &num) ) { if( num == 0 ) {//为零时, 输入结束,不用做处理 printf("0 0 0\n"); continue; } for( i=0; i<num; ++i ) {//录取num个整数到数组a中 scanf("%d", &a[i]); } num_1.sum = 0; num_1.end_site = 0; num_1.first_site = 0;//存最终结果 num_2.sum = 0; num_2.end_site = 0; num_2.first_site = 0;//临时存放中间结果 i = 0; while( i != num ) { if( a[i] > 0 ) { num_2.sum = 0; num_2.sum = +a[i]; num_2.first_site = i; ++i; loop: while( i!=num && a[i]>0 ) { num_2.sum += a[i]; ++i; } if( i == num ) { num_2.end_site = i-1; if( num_1.sum<num_2.sum ) { num_1.sum = num_2.sum; num_1.first_site = num_2.first_site; num_1.end_site = num_2.end_site; } } else { num_2.end_site = i-1; temp = 0; while( i!=num && a[i]<=0 ) { temp += a[i]; ++i; } if( i==num && num_1.sum<num_2.sum ) { num_1.sum = num_2.sum; num_1.first_site = num_2.first_site; num_1.end_site = num_2.end_site; } else { if( abs(temp)>a[i] && num_1.sum<num_2.sum ) { num_1.sum = num_2.sum; num_1.first_site = num_2.first_site; num_1.end_site = num_2.end_site; } else { num_2.sum += temp; goto loop; } } } } else { ++i; } } if( num_1.sum == 0 ) { num_1.end_site = num-1; num_1.first_site = 0; } printf("%d %d %d\n", num_1.sum, a[num_1.first_site], a[num_1.end_site] ); } return 0; } 只有本站会员才能查看附件,请 登录 |
我的代码实在返现不知道错在哪儿了,运行数据测试不正确;
哪位大哥帮我看看呗,感激不尽!
代码:
程序代码:#include<stdio.h>
#include<stdlib.h>
#define MAX 10001
//动态规划:状态方程:c[n]=max{c[n-1]+a[n],a[n]};
int main(){
int K;
while(scanf("%d",&K)!=EOF){
if(K==0)break;
int a[MAX],i;
for(i=0;i<K;i++){
scanf("%d",&a[i]);
}
int c[MAX],start[MAX],maxNum,start0,end;
c[0]=a[0];//保存最大值;
start[0]=a[0];
for(i=1;i<K;i++){
if(c[i-1]+a[i]>a[i]){
start[i]=start[i-1];
c[i]=c[i-1]+a[i];
}
else{
start[i]=a[i];
c[i]=a[i];
}
}
maxNum=c[0];
start0=a[0];
end=a[0];
for(i=1;i<K;i++){
if(maxNum<a[i]){
maxNum=a[i];
start0=start[i];
end=a[i];
}
}
if(maxNum<0){
printf("0 %d %d\n",a[0],a[K-1]);
}
else{
printf("%d %d %d\n",maxNum,start0,end);
}
}
}
#include<stdlib.h>
#define MAX 10001
//动态规划:状态方程:c[n]=max{c[n-1]+a[n],a[n]};
int main(){
int K;
while(scanf("%d",&K)!=EOF){
if(K==0)break;
int a[MAX],i;
for(i=0;i<K;i++){
scanf("%d",&a[i]);
}
int c[MAX],start[MAX],maxNum,start0,end;
c[0]=a[0];//保存最大值;
start[0]=a[0];
for(i=1;i<K;i++){
if(c[i-1]+a[i]>a[i]){
start[i]=start[i-1];
c[i]=c[i-1]+a[i];
}
else{
start[i]=a[i];
c[i]=a[i];
}
}
maxNum=c[0];
start0=a[0];
end=a[0];
for(i=1;i<K;i++){
if(maxNum<a[i]){
maxNum=a[i];
start0=start[i];
end=a[i];
}
}
if(maxNum<0){
printf("0 %d %d\n",a[0],a[K-1]);
}
else{
printf("%d %d %d\n",maxNum,start0,end);
}
}
}
[ 本帖最后由 xiajun0706 于 2011-2-25 18:08 编辑 ]