/* 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]
。 是否有可能提供类似于递归公式的递归解决方案?
LIS :这是遵循LIS定义的简单解决方案。 假设A是数字的输入数组, N是A的大小。
int L[51]; int res=-1; for(int i=0;i
时间复杂度:O(N 2 )。
以上就是c/c++开发分享最长增加子序列中的荒谬条件相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/519779.html