TOPIC
Sugestão de Algoritmo
fbrunodr asked 3 years ago
Alguma sugestão de algoritmo? Utilizei o seguinte código com O(n) de tempo, porém continuo recebendo TLE.
#include<iostream>
#include<vector>
using namespace std;
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++;
}
if( j-i > maxCount )
return j - i + 1;
else
return maxCount + 1;
}
int main(){
int N, L; cin >> N >> L;
while(N != 0){
if( N == 1 ){
cout << 0 << endl;
continue;
}
vector<int> differences;
int previousNumber; cin >> previousNumber;
for(int i = 0; i < L - 1; i++){
int number; cin >> number;
differences.push_back(number - previousNumber);
previousNumber = number;
}
cout << N - getLargestSubsequenceSize( differences, N - 1 ) << endl;
cin >> N >> L;
}
return 0;
}