TOPIC

Sugestão de Algoritmo

Francisco Bruno Dias asked 1 year 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;
}

Remember not post solutions. Your post may be reviewed by our moderators.

  • feodorv replied 1 year ago

            if( N == 1 ){
                cout << 0 << endl;
                continue;
            }

    You should read all L positive integers from the input, you can't do continue here.