Trouver une sous-séquence (petite-big-medium)

Question

Étant donné une liste de $ n $ Numéros entiers non répétitifs $ l: = (x_1, points, x_n) $ Développez un algorithme qui décide s'il y a $ x_ {i_1}, x_ {i_2}, x_ {i_3} in l $ tel que $ i_1

La déclaration suggère également d'utiliser la stratégie "Divide & Conquer".

Mon essai était ce qui suit:

J'ai lu le vecteur de gauche à droite

• Si la liste passe de l'augmentation à la diminution, il est clair que le dernier numéro de lecture est inférieur au maximum de la liste actuellement lue. Donc, s'il est supérieur au minimum de la liste actuelle, nous pouvons arrêter. Cette comparaison peut être effectuée dans $ mathcal {o} (1) $ si nous gardons une trace du minimum de la liste actuellement lue.
• Si la liste passe de la diminution à l'augmentation, je recherche le premier nombre $ m $ dans la liste qui est un minimum local et il est inférieur au dernier numéro de lecture $ c $. Et puis je cherche un maximum local apparaissant après $ M $ qui est supérieur à $ C $. Si les deux recherches réussissent, nous pouvons nous terminer. Ces recherches peuvent être effectuées dans $ mathcal {o} ( log n) $ time si nous gardons une trace des maximums locaux et des minimums locaux actuellement trouvés (recherche binaire).
• Si la liste continue d'augmenter, nous faisons de même que dans l'étape précédente.
• Si la liste continue de diminuer, ne faites rien.

La complexité est donc $ Mathcal {o} (n log n) $. Je pense que la stratégie est bonne, mais un juge en ligne l'a rejeté. Je ne sais pas si cela est dû à un bogue idiot ou parce que la stratégie est vraiment fausse.

Quoi qu'il en soit, en voyant les statistiques des personnes qui ont résolu le problème, ma solution est si la mémoire est consommée, donc je pense vraiment que cela peut être mieux fait.

Une idée?