问题标题: 酷町堂：3847 最大连续子序列1

Question

0

已解决

汪恺恒

中级启示者

题目描述 Description

给出一个大小为n的序列，元素分别为，a1 a2 an … an。序列中点如下图所示。现在要求一个跨过中点（粗的黑线）的连续序列，这个连续序列的和最大。

输入描述 Input Description

第一行，一个整数，n
第二行，n个整数，a1 a2 … an

输出描述 Output Description

跨过中点且和最大的连续子序列

WA40

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n,a[105],mid,ans1,ans2;
int main(){
    cin>>n;
    mid=(n+1)/2;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
	ans1=a[mid+1];
	ans2=a[mid];
	for(int i=mid+2;i<=n;i++){
		if(ans1+a[i]>ans1){
			ans1+=a[i];
		}
		else break;
	}
	for(int i=mid-1;i>=1;i--){
		if(ans2+a[i]>ans2) ans2+=a[i];
		else break;
	}
	cout<<ans1+ans2;
    return 0;
}

汪恺恒在2021-04-02 20:31:42追加了内容

d

Answer 1

已采纳

张帆

中级天翼

 if(n%2==0){
        int pos=n/2;
        int ans1=a[pos],ans2=a[pos+1];
        f[pos]=a[pos];
        f[pos+1]=a[pos+1];
        for(int i=pos-1;i>=1;i--){
            f[i]=f[i+1]+a[i];
            ans1=max(ans1,f[i]);
        }
        for(int i=pos+2;i<=n;i++){
            f[i]=f[i-1]+a[i];
            ans2=max(ans2,f[i]);
        }
        cout<<ans1+ans2;
    }

n%2==1自行推导