# PBinfo #3844 – KSum – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N și K apoi un vector cu N elemente, din acest vector care este suma maximă a unei secvențe (elemente adiacente) de lungime cel puțin K. A zis să vă întrebe pe voi cum se face.

Date de intrare
Fișierul de intrare ksum.in conține pe prima linie numerele N și K, pe următoarea linie N elemente întregi reprezentând elementele vectorului.

Date de ieșire
Fișierul de ieșire ksum.out va conține pe prima linie numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K.

Restricții și precizări

1 ≤ K ≤ n ≤ 100.000
numerele de pe a doua linie a fișierului de intrare vor fi din intervalul [-1.000, 1.000].

Exemplu:
ksum.in

6 3
5 4 -10 1 2 3
ksum.out

6
Explicație
Secvența căutată este [4, 6] cu suma 1 + 2 + 3 = 6.

## Cod sursă C++

```cpp
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ksum.in");
ofstream fout("ksum.out");
int n,k,s[100005],m[100005];
int main(){
    fin>>n>>k;
    for(int i=1;i<=n;i++)fin>>s[i];
    for(int i=1;i<=n;i++)s[i]+=s[i-1];
    int mx(s[k]);
    m[n]=s[n];
    for(int i=n-1;i>=1;i--)m[i]=max(m[i+1],s[i]);
    for(int i=1;i<=n-k+1;i++)mx=max(mx,m[i+k-1]-s[i-1]);
    fout<<mx;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3844)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3844/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3844/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)