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