Pitanje oko zadatka Najduzi rastuci podniz - DP

Pitanje oko zadatka Najduzi rastuci podniz - DP

Slican zadatak je bio i u lekciji, nakon sto sam sam pokusao da odradim zadatak i imao TLE na dva poslednja test primera napisao sam kod od algoritma iz lekcije i izbacio nepotrebne delove (zato sto se zadatak malo razlikovao) i isto sam imao TLE na dva poslednja test primera. Da li moze neko da mi kaze sta je lose u mom resenju i da mi napise resenje koje radi sa svih 8 test primera? Ovo je moj kod:

#include<iostream>
#include<vector>
using namespace std;
void nnp(vector<int> x,int n){
    vector<int> d(n);
    d[0]=1;
    for(int i=0;i<=n-1;i++){
	    int dmax=0;
	    for(int k=0;k<=i-1;k++){
		    if(x[k]<x[i] && dmax<d[k]){
			    dmax=d[k];
		    }
	    }
	    d[i]=dmax+1;
    }
    cout<<d[n-1];
}
int main(){
    int n;
    cin>>n;
    vector<int> niz(n);
    for(int i=0;i<n;i++){
	    cin>>niz[i];
    }
    nnp(niz,n);
    return 0;
}

Link ka zadatku ----> https://petlja.org/BubbleBee/r/Problems/LSA

Dobijaš TLE pošto tvoj algoritam ima složenost O(n^2), a da bi rešio zadatak potrebna ti je složenost O(nlogn). Ovo ti može pomoći. Vodi računa o ulaznim podacima pošto koristiš int, a trebao bi long long (u ovom zadatku), takođe kada imaš dosta ulaznih podataka koristi scanf/print ili ovo da poboljšaš vreme izvršenja.

2 Likes