Ho un vector<int> num , voglio ottenere la taglia del subarray più lungo con la somma minore o uguale a k.
Il mio approccio: O (n ^ 2). Ripeti per ogni elemento dell'array.
Possiamo fare di meglio?
Nota: non ho bisogno del subarray reale più lungo, ma solo della sua dimensione. Quindi il valore di ritorno è int.
Supponendo che il vettore contenga solo numeri interi non negativi:
int getLargestSubsequenceSize(vector<int>& myVector, int k){
int maxCount = 0;
int i=0,j=0;
int sum = 0;
while(j < myVector.size()){
sum += myVector[j];
if(sum > k){
int currCount = j-i;
if(currCount > maxCount)
maxCount = currCount;
sum -= myVector[i];
i++;
}
j++;
}
return maxCount;
}
La funzione precedente ha due indici (i,j) . j incrementerà e aggiungerà il numero corrente alla somma finché la somma diventa maggiore di k . Una volta che è maggiore, calcoleremo la lunghezza di questa sotto-sequenza e controlleremo se è più grande della sottosequenza precedente. Se sì, aggiorneremo il maxCount. Ora, incrementeremo l'indice inferiore (i) e ripeterò il processo. Complessità del tempo = O (n)
Leggi altre domande sui tag c++ array dynamic-programming