题解 | #求连续子数组的最大和#

求连续子数组的最大和

http://www.nowcoder.com/practice/8705437354604a7cb9ba7bf959e42de6

include<stdio.h>

int max(int a,int b){
return a>b?a:b;
}
int main(){
int in[10000];
int n=0;
bool isAll_=true;
do{
scanf("%d", &in[n++]);
if(in[n-1]>0) isAll_=false;
}while(getchar()!='\n');

if(isAll_) printf("0\n");
else{
    int dp;//dp[j]是必须包含元素in[j]的向前连续延申的最大子段和
    dp=in[0]>0?in[0]:0;
    int maxv=dp;
    for(int i=2;i<=n;i++){
        if(dp>0) dp+=in[i-1];
        else dp=in[i-1];
        if(maxv<dp) maxv=dp;
    }
    printf("%d\n", maxv);
}

}

全部评论

相关推荐

头像
05-12 09:14
点赞 评论 收藏
转发
点赞 评论 收藏
转发
2 收藏 评论
分享
牛客网
牛客企业服务