# PBinfo #3846 – KSum2 – 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, K și W 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 și cel mult W. A zis să vă întrebe pe voi cum se face.

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

Date de ieșire
Fișierul de ieșire ksum2.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 și cel mult W.

Restricții și precizări

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

Exemplu:
ksum2.in

6 3 4
5 4 -10 1 2 3
ksum2.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("ksum2.in");
ofstream fout("ksum2.out");
int n,k,s[100005],dp[100005][18],lg[100005],w;
int qr(int st,int dr){
    int l(lg[dr-st+1]);
    return max(dp[st][l],dp[dr-(1<<l)+1][l]);
}
int main(){
    fin>>n>>k>>w;
    for(int i=2;i<=n;i++){
        lg[i]=lg[i-1];
        if(!(i&(i-1)))lg[i]++;
    }
    for(int i=1;i<=n;i++)fin>>s[i];
    for(int i=1;i<=n;i++)s[i]+=s[i-1],dp[i][0]=s[i];
    for(int i=1;(1<<i)<=n;i++){
        for(int j=1;j+(1<<i)-1<=n;j++){
            dp[j][i]=max(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
        }
    }
    int mx(s[k]);
    for(int i=1;i<=n-k+1;i++)mx=max(mx,qr(i+k-1,min(n,i+w-1))-s[i-1]);
    fout<<mx;
    return 0;
}
```

## Resurse

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