c/c++语言开发共享最长增加子序列中的荒谬条件

/* 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 %dn", lis( arr, n )); getchar(); return 0; 

令arr [0..n-1]为输入数组，L（i）为LIS的长度，直到索引i，使得arr [i]是LIS的一部分，arr [i]是LIS中的最后一个元素，然后L（i）可以递归写为。 L（i）= {1 + Max（L（j））}其中j <i且arr [j] <arr [i]并且如果不存在这样的j则L（i）= 1。

在上面的实现中， if (arr[i-1] max_ending_here) ，我无法理解条件的使用/重要性。 它甚至看起来不像递归公式，那么为什么需要它。当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那么为什么我们需要比较arr[i-1] < arr[n-1] 。 是否有可能提供类似于递归公式的递归解决方案？

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