Cod sursa(job #3149890)
| Utilizator | Data | 13 septembrie 2023 13:00:41 | |
|---|---|---|---|
| Problema | Subsecventa de suma maxima | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.53 kb |
#include <bits/stdc++.h>
const int nmax = 6e6;
using namespace std;
ifstream in("ssm.in");
ofstream out("ssm.out");
int v[nmax];
int main()
{
//two pointers
int n;
in >> n;
for(int i=0;i<n;i++){
in >> v[i];
}
int r1, r2;
int st = 0;
long long s = 0;
long long mx = 0;
for(int dr = 0; dr < n; dr++){
s+=v[dr];
while(s<0 && st<dr){
s-=v[st];
st++;
}
if(mx<s){
r1 = dr;
r2 = st;
}
mx = max(mx, s);
}
out << mx << " " << r1+1 << " " << r2+1;
}
