Cod sursa(job #3221377)

Utilizator Wolf98Vlad Munteanu Wolf98 Data 6 aprilie 2024 21:10:35
Problema Subsecventa de suma maxima Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

int v[6000005];
int main() {
    ifstream fin ("ssm.in");
    ofstream fout ("ssm.out");
    int n;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }
    int maxSum = -999999999, maxSt = -1, maxDr = -1;
    int curSum = 0, curSt = 1; // curDr = va fi i ul din for
    
    for (int i = 1; i <= n; ++i) {
        curSum += v[i]; //imi adaug v[i] la suma curenta
        
        if (curSum > maxSum) {
            maxSum = curSum;
            maxSt = curSt;
            maxDr = i;
        }
        
        // tre sa verificam daca vrem sa pastram suma curenta si pentru i + 1
        // o pastram doar daca este pozitiva
        // daca este negativa vom incepe o suma noua de la i + 1
        
        if (curSum < 0) {
            curSum = 0;
            curSt = i + 1;
        }
    }
    fout << maxSum << ' ' << maxSt << ' ' << maxDr;
    return 0;
}