Cod sursa(job #3180119)

Utilizator MateiAlex24Diamandi Matei MateiAlex24 Data 4 decembrie 2023 17:34:36
Problema Subsecventa de suma maxima Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>

using namespace std;


ifstream fin("ssm.in");
ofstream fout("ssm.out");

int main()
{
    long long int n, v[50002], k, suma_max=0;
    fin>>n>>k;
    for (int i=1; i<=n; i++){
        fin>>v[i];
        suma_max += v[i];
    }
    
    long long int poz1=1, poz2=n, poz1max=1, poz2max=n;
    // 0 -6 2 1 4 -1 3 -5
    // idee: stergem ultimul/primul element depinde care e mai mic
    while (poz2-poz1 >= 0){
        long long int suma=0;
        for (int i=poz1; i<=poz2; i++){
            suma += v[i];
        }
        if (suma > suma_max){
            suma_max = suma;
            poz1max = poz1;
            poz2max = poz2;
        }
        if (v[poz1] > v[poz2])
            poz2--;
        else
            poz1++;
    }
    
    fout<<suma_max<<" "<<poz1max+1<<" "<<poz2max+1;

    return 0;
}