Cod sursa(job #2668990)

Utilizator tudorcioc5Cioc Tudor tudorcioc5 Data 5 noiembrie 2020 20:09:51
Problema Secventa 2 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <climits>
using namespace std;

const int MAX_LENGTH = 50002;

int main (void){
    ifstream fin ("secv2.in");

    int length, sequenceLength;
    fin>>length>>sequenceLength;


    int partialSum[MAX_LENGTH] = {};
    int minimumSum[MAX_LENGTH] = {};

    for (int i=1; i<=length; i++){
        int number;
        fin>>number;

        partialSum[i] = partialSum[i-1] + number;

    }
    fin.close();

    minimumSum[1] = 1;
    int sumToCompare = partialSum[1];
    int positionSumToCompare = 1;

    for (int i=2; i<=length; i++){
        if (partialSum[i] < sumToCompare){
            minimumSum[i] = i;
            positionSumToCompare = i;
            sumToCompare = partialSum[i];
        }else{
            minimumSum[i] = positionSumToCompare;
        }

    }

    int right;
    int maxSum = INT_MIN;

    for (int i = sequenceLength; i<=length; i++){
        int aux = partialSum[i];
        aux -= partialSum[minimumSum[i-sequenceLength + 1]];

        if (aux > maxSum){
            maxSum = aux;
            right = i;
        }
    }

    ofstream fout ("secv2.out");
    fout<<minimumSum[right - sequenceLength + 1] + 1<<" "<<right<<" "<<maxSum<<"\n";
    fout.close();



    return 0;
}