Se dă un șir cu n numere naturale și un număr k.

Cerinţa

Să se determine o secvență de elemente de lungime k cu suma elementelor maximă.

Date de intrare

Fişierul de intrare secvk.in conţine pe prima linie numerele n și k, iar pe a doua linie n numere naturale separate prin spaţii.

Date de ieşire

Fişierul de ieşire secvk.out va conţine pe prima linie k numere, reprezentând elementele secvenței cerute.

Restricţii şi precizări

1 ≤ k ≤ n ≤ 100.000
numerele de pe a doua linie a fişierului de intrare vor fi mai mici decât 1000
dacă există mai multe secvențe de lungime k cu suma maximă se va afișa prima

Exemplu

secvk.in

8 3
5 6 1 2 6 6 4 3

secvk.out

6 6 4

Explicație

Sumele care se pot obține sunt: 12 9 9 14 16 13. Suma maximă este 16 și se obține pentru secvența 6 6 4

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema SecvK:

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

int n, k, a[100005], s[100005];


int main(){
    ifstream fin("secvk.in");
    ofstream fout("secvk.out");
    fin >> n >> k;
    for(int i=1;i<=n;++i)
        fin >> a[i], s[i] = s[i-1]+a[i];
    int st=0,dr=0,smax = 0;
    for(int i=k;i<=n;++i)
        if(s[i]-s[i-k] > smax)
            smax = s[i]-s[i-k], st = i-k+1, dr = i;
    for(int i=st ; i<=dr ; ++i)
        fout << a[i] << " ";
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #134 SecvK

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #134 SecvK de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #134 SecvK