先考虑一只鞋子的情况，就是求序列的最大子段和，一双鞋子即为，序列中最大的两段子段和。

记

• $f_i$ 表示 以 $i$ 为结尾 的 最大子段和
• $pre_i$ 表示 $1- i$ 中的最大子段和
• $g_i$ 表示 以 $i$ 为开头 的 最大子段和
• $suf_i$表示 $i - n$ 中的最大子段和

$g,suf$ 同理 答案为 $pre_i + suf_{i+1}$ 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,c,a[1000005],g1[1000005],g2[1000005],f1[1000005],f2[1000005],ans=-1e9+7;
signed main() {
	cin>>n;
	g1[0]=g2[n+1]=-1e18;
	for(int i=1; i<=n; i++)cin>>a[i];
	for(int i=1; i<=n; i++) f1[i]=max(f1[i-1]+a[i],a[i]);
	for(int i=1;i<=n;i++) g1[i]=max(g1[i-1],f1[i]);
	for(int i=n;i>=1;i--) f2[i]=max(f2[i+1]+a[i],a[i]);
	for(int i=n;i>=1;i--) g2[i]=max(g2[i+1],f2[i]);
	for(int i=0;i<=n;i++)ans=max(g1[i]+g2[i+1],ans);
	if(ans<=0)cout<<"no solution"<<endl;
	else cout<<ans<<endl;
	return 0;
}