Cod sursa(job #2907960)

Utilizator cyg_TheoPruteanu Theodor cyg_Theo Data 31 mai 2022 23:18:33
Problema Subsecventa de suma maxima Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;
const int NMAX = 2e5+5;

int v[NMAX];
ll dp[NMAX];
int fi[NMAX];
int len[NMAX];

int main(){
	freopen("ssm.in", "r", stdin);
	freopen("ssm.out", "w", stdout);

	int n;
	scanf("%d", &n);

	for(int i=0; i<n; ++i)
		scanf("%d", &v[i]);

	dp[0] = v[0];
	for(int i=1; i<n; ++i)
		if(dp[i-1] < 0){
			dp[i] = v[i];
			fi[i] = i+1;
			len[i] = 0;
		}else{
			dp[i] = dp[i-1] + v[i];
			fi[i] = fi[i-1];
			len[i] = len[i-1] + 1;
		}

	int maxs = 0;
	for(int i=1; i<n; ++i)
		if(dp[maxs] < dp[i])
			maxs = i;

	printf("%lld %d %d\n", dp[maxs], fi[maxs], fi[maxs] + len[maxs]);

	return 0;
}