# Four Segments

Four Segments

``````3
-1 2 3
``````

``0 1 3``

``````#include<stdio.h>
long long int  ans=-1e9;
using namespace std;
int main()
{
int i,j,k;
long long int a[5010];
a[0]=0;
int n,m,t;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&t);
a[i]=a[i-1]+t;
}
int t1,t2;
int d1,d2,d3;
for(j=0;j<=n;j++)
{
t1=0;
for(i=0;i<=j;i++)
{
if(a[i]>a[t1])
{
t1=i;
}
}
t2=j;
for(k=j;k<=n;k++)
{
if(a[k]>a[t2])
{
t2=k;
}
}
if(a[t1]+a[t2]-a[j]>ans)
{
ans=a[t1]+a[t2]-a[j];
d1=t1;
d2=j;
d3=t2;
}
}
printf("%d %d %d",d1,d2,d3);
return 0;
}``````

``````#include<bits/stdc++.h>
#define fin             freopen("in.txt","r",stdin)
typedef long long ll;
using namespace std;
const int maxn = 5005;
int a[maxn],l[maxn],r[maxn],x,y,z;
ll sum[maxn],ans=-0x3f3f3f3f;
int main() {
int n;
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i], sum[i]=sum[i-1]+a[i];
for (int i=1;i<=n;i++) {
if (sum[i]>sum[ l[i-1] ]) l[i]=i;
else l[i]=l[i-1];
}
r[n]=n;
for (int i=n-1;i>=0;i--) {
if (sum[i]>=sum[ r[i+1] ]) r[i]=i;
else r[i]=r[i+1];
}
for (int i=0;i<=n;i++)
if(sum[l[i]]-sum[i]+sum[r[i]]>ans) {
ans=sum[l[i]]-sum[i]+sum[r[i]];
x=l[i],y=i,z=r[i];
}
cout<<x<<" "<<y<<" "<<z<<endl;
return 0;
}``````