Cod sursa(job #2550424)
| Utilizator | Data | 18 februarie 2020 19:50:07 | |
|---|---|---|---|
| Problema | Subsecventa de suma maxima | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.56 kb |
#include <bits/stdc++.h>
using namespace std;
int a[6000100],dp[6000100];
int rs=INT_MIN,n,sf,inc;
int main(){
ifstream cin("ssm.in");
ofstream cout("ssm.out");
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
dp[i]=max(dp[i-1]+a[i],a[i]);
if(dp[i]>rs){
rs=dp[i];
sf=i;
}
}
cout<<rs<<' ';
int i=sf;
if(rs<0) while(rs<0){rs-=a[i];i--;}
else while(rs>0){rs-=a[i];i--;}
while(a[i]==0) i--;
cout<<i+1<<' '<<sf;
return 0;
}
