Marathon Training (run) - TLE in 4 testcases

Sto provando a risolvere il problema Marathon Training (run), ma il codice che ho scritto prende TLE in 4 casi (005, 009, 010, 036).

L’idea è che per ogni D[i], itero da D[i + 1] a D[N - 1]: quando trovo un valore che è più grande di tutti i precedenti fino a D[i] compreso, ho trovato una sequenza valida e aggiorno il risultato; se, invece, trovo un valore che è più piccolo di D[i], torno al ciclo esterno.
Il ciclo esterno si interrompe se non è più possibile, partendo da i, trovare una sequenza più lunga dell’attuale risultato.

#include <bits/stdc++.h>

int main()
{
    std::ifstream ifs("input.txt");
    std::ofstream ofs("output.txt");

    std::ios::sync_with_stdio(false);
    ifs.tie(0);

    int N = 0;
    ifs >> N;

    std::vector<int> distances;
    for(int i = 0, D; i < N; ++i) {
        ifs >> D;
        distances.push_back(D);
    }

    int ret = 1;

    for(int i = 0; N - i > ret; ++i) {
        int mx = 0;

        for(int j = i + 1; j < N; ++j) {
            if(distances[j] < distances[i]) break;

            if(distances[j] >= mx) {
                mx = distances[j];

                if(j - i + 1 > ret) {
                    ret = j - i + 1;
                }
            }
        }
    }

    ofs << ret;

    return 0;
}

L’ho risolto tempo fa e non ricordo tutto chiaramente ma, a grandi linee, ho lavorato trovando inizialmente i valori minimi mini[i] dove mini[i] è il valore sotto il quale non scende nessuno dei D che vengono prima di D[i] i compreso. Poi ho creato le coppie {D[i],i]} e le ho ordinate decrescenti (occhio ai valori uguali di D).
Infine per ogni massimo ho trovato il minimo che lo precede, trovato la lunghezza, marcato come visitata l’intera gamma in modo da scartare l’elaborazione di massimi che cadono in gamme già visitate. termino quando la somma dei buchi liberi è inferiore uguale alla gamma già trovata.
In ogni caso i primi 3 test case che ti danno TLE appartengono al subtask con D<=1 e possono essere gestiti rapidamente in maniera diversa.
Ci possono essere accorgimenti per velocizzare il tutto tipo scartare una sequenza iniziale decrescente. (comunque direi che le streaks non si sovrappongono)

Comunque con una piccola modifica il tuo codice fa 100 (in 60ms circa) basta che dopo aver trovato uno streak che va da i fino a j riparti da j+1 e non da i+1:

    .......
    int ret = 1;
    int k;
    for(int i = 0; N - i > ret; ++i) {
        int mx = 0;
        k=i;

        for(int j = i + 1; j < N; ++j) {
            if(distances[j] < distances[i]) break;

            if(distances[j] >= mx) {
                mx = distances[j];
                k=j;
                if(j - i + 1 > ret) {
                    ret = j - i + 1;
                }
            }
        }
    i=k;
    }
  .....