Najdłuższy spójny ciąg o zadanej sumie

Question

Hejka 

Mam problem ze znalezieniem najdłuższego spójnego ciągu o zadanej sumie 

np. dla sumy 4 i ciągu 3 -2 6 1 -1 5 (ciąg -2 6 1 -1) 

Napisałam ten program ale sam kod ma złożoność n^2  (chyba) 

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,s;
    vector<int> v;
    cin>>n>>s;
    v.resize(n);
    int suma=0;
    for(int i=0; i<n;i++) 
    {
        cin>>v[i];
        suma=suma+v[i];
    }
    int templ=0, maxil=0;
    int temps=0;
    for(int i=0; i<n; i++){
        for(int j=i; j<n; j++){
           temps=temps+v[j], templ++;
           if(temps==s and templ>maxil) maxil=templ;
           //cout<<temps<<endl;
        }
        temps=0, templ=0;
    }
    if(maxil==0)cout<<"BRAK";
    else cout<<maxil;



}

Potrzebuję jednak czegoś o lepszej złożoności, myślałam o programowaniu dynamicznym jednak nie wiem jak się do tego zabrać. 

Dziękuję za wszystkie wskazówki <3 

Answer 1

Najlepiej to zrobić sumami prefiksowymi. Załóżmy, że suma[i] to suma prefiskowa pierwszych i elemntów ciągu. Dodatkowo powiedzmy, że najdłuższy spójny ciąg o danej sumie ma się kończyć na pozycji j. Wtedy szukamy takiej pozycji i (i < j), że suma[j] - suma[i] = zadana suma.

Musisz się jeszcze tylko zastanowić jak to zaimplementować.

Comments

Masz podane jaki jest limit pamięci albo jakie są ograniczenia na n, s lub wartości ciągu?

---

limit 32 mb

1<=n<=10^6

|s|<=10^6

elementy ciągu |x|<=10^6

---

To na pewno pom, para i mapa muszą być typu long long. Jeżeli to wciąż będzie za mało to spróbuj pozbyć się tablicy pom, bo ona jest tak naprawdę niepotrzebna

---

Long long zajmie więcej, ale problem jest taki, że zwykły int może nie pomieścić wszystkich wartości. W najgorszym przypadku dostaniesz sumę prefisową równą 10^12, a int może przyjąć co najwyżej 10^9

---

Faktycznie, rozumiem

Answer 2

Musisz to zrobić gąsienicą. Trzymasz początek i koniec pewnego segmentu w tablicy  i pamiętasz jego sumę, jeżeli suma jest za mała to rozszerzasz okienko o kolejny element (przesuwasz koniec o jeden element do przodu), jeżeli za duża to przesuwasz początek o jeden element do przodu (zmniejszasz okienko)

Comments

To może nie działać gdy elementy ciągu są ujemne

---

Rzeczywiście teraz zauważyłem, że przecież są ujemne