Condition absurde dans la plus longue sous-séquence croissante

/* A Naive recursive implementation of LIS problem */ #include #include /* To make use of recursive calls, this function must return two things: 1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose 2) Overall maximum as the LIS may end with an element before arr[n-1] max_ref is used this purpose. The value of LIS of full array of size n is stored in *max_ref which is our final result */ int _lis( int arr[], int n, int *max_ref) { /* Base case */ if(n == 1) return 1; int res, max_ending_here = 1; // length of LIS ending with arr[n-1] /* Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs to be updated, then update it */ for(int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i-1]  max_ending_here) max_ending_here = res + 1; } // Compare max_ending_here with the overall max. And update the // overall max if needed if (*max_ref < max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() int lis(int arr[], int n) { // The max variable holds the result int max = 1; // The function _lis() stores its result in max _lis( arr, n, &max ); // returns max return max; } /* Driver program to test above function */ int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr)/sizeof(arr[0]); printf("Length of LIS is %d\n", lis( arr, n )); getchar(); return 0; 

Soit arr [0..n-1] le tableau d’entrée et L (i) la longueur de LIS jusqu’à l’indice i, de sorte que arr [i] fait partie de LIS et arr [i] est le dernier élément de LIS, alors L (i) peut être écrit récursivement comme. L (i) = {1 + Max (L (j))} où j <i et arr [j] <arr [i] et s'il n'y a pas un tel j alors L (i) = 1.

Dans l’implémentation ci-dessus, je ne suis pas en mesure de comprendre l’utilisation / l’importance de la condition if (arr[i-1] max_ending_here) . Cela ne ressemble même pas à la formule récursive, alors pourquoi est-il nécessaire.Lorsque L(i)/*is just*/ = { 1 + Max ( L(j) ) } where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1 pourquoi avons-nous besoin de comparer arr[i-1] < arr[n-1] . Est-il possible de proposer une solution récursive similaire à la formule récursive?

LIS : Voici une solution simple suivant la définition de LIS. En supposant que A est le tableau de nombres en entrée, N est la taille de A.

 int L[51]; int res=-1; for(int i=0;i 

Complexité temporelle: O (N 2 ).