2479.txt

acm pku 2479题

完全是bug...居然放错了地方..而且每次只测试一个用例的话也都是对的...如果做过 1050 ,,这个题目是很好理解的..我刚开始用的 o(n^2) 的算法,,tle 了,,其实已经离答案不远了...

过了的代码:

#include <iostream>
#include <stdio.h>
using namespace std;

int num[50002],n;
int ltr[50002],rtl[50002];

void maxltr(){
    int max=num[1];
    int sum=num[1];
    ltr[1]=max;
    for(int lt=2;lt<=n;lt++){
        if(sum>0) sum+=num[lt];
        else sum=num[lt];
        if(sum>max) max=sum;
        ltr[lt]=max;
        //printf("ltr[%d]=%d\n",lt,max);
    }
}

void maxrtl(){
    int max=num[n];
    int sum=num[n];
    rtl[n]=max;
    for(int lt=n-1;lt>=1;lt--){
        if(sum>0) sum+=num[lt];
        else sum=num[lt];
        if(sum>max) max=sum;
        rtl[lt]=max;
        //printf("rtl[%d]=%d\n",lt,max);
    }
}

int main(){
    int tn;
    int lt;
    int maxall; ///maxall=-600000!!!!!! 居然放到了这里....
    cin>>tn;
    while(tn--){
        cin>>n;
        for(lt=1;lt<=n;lt++) scanf("%d",&num[lt]);
        maxltr();
        maxrtl();
        maxall=-600000000; /////should be here
        for(lt=1;lt<n;lt++) maxall>?=(ltr[lt]+rtl[lt+1]);
        printf("%d\n",maxall);
    }
}


bug bug bug


tle 的 :

#include <iostream>
#include <stdio.h>
using namespace std;

int num[50002],n;

int max(int st,int en){
    int max=num[st];
    int sum=num[st];
    for(int lt=st+1;lt<=en;lt++){
        if(sum>0){
            sum+=num[lt];
            if(sum>max) max=sum;
        }
        else{
            sum=num[lt];
            if(sum>max) max=sum;
        }
    }
    return max;
}

int main(){
    int tn;
    int lt;
    int max1,max2,maxall;
    cin>>tn;
    while(tn--){
        cin>>n;
        for(lt=1;lt<=n;lt++) scanf("%d",&num[lt]);
        maxall=-60000000;
        max1=max2=-600000000;
        for(lt=1;lt<n-2;lt++){ //这里重复计算了很多次
            max1=max(1,lt);
            max2=max(lt+1,n);
            if(max1+max2 > maxall) maxall=max1+max2;
        }
        cout<<maxall<<endl;
    }
}