在最长递增Subquence荒诞条件 [英] Absurd condition in Longest Increasing Subquence

问题描述

    /* A Naive recursive implementation of LIS problem */
    #include<stdio.h>
    #include<stdlib.h>

    /* 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] < arr[n-1] && res + 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;

让改编[0..N-1]是输入阵列和L（i）是LIS直到索引i的长度，使得改编[i]为LIS的一部分，并改编[i]为所述最后一个元件在LIS，则L（ⅰ）可以递归写成。 L（I）= {1 +最大值（L（J））}，其中J＆LT;我和ARR [J] LT;改编[i]和如果不存在这样的Ĵ则L（ⅰ）= 1

Let arr[0..n-1] be the input array and L(i) be the length of the LIS till index i such that arr[i] is part of LIS and arr[i] is the last element in LIS, then L(i) can be recursively written as. L(i) = { 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]，常用3 [N-1]安培;＆功放; RES + 1 ＆GT; max_ending_here）。它甚至没有看起来像递推公式，那么它为什么needed.When L（I）/ *就是* / = {1 +最大值（L（J））}，其中J＆LT;我和ARR [J] LT;改编[i]和如果不存在这样的Ĵ则L（ⅰ）= 1 thenwhy做我们需要比较改编[I-1]; ARR [N-1] 。是否有可能来一个递归解决方案，这是类似的递推公式？

In the above implementation , i am not able to understand the use/importance of the condition if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here). It's doesn't even looks like the recursive formula , then why is it needed.When 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 thenwhy do we need to compare arr[i-1] < arr[n-1]. Is it possible to come with a recursive solution which is similar to the recursive formula?

推荐答案

LIS ：这里有以下LIS的定义，一个简单的解决方案。 假定的 A 是一个数字的输入数组， N 是大小的 A

LIS: Here's a simple solution following the definition of LIS. Assuming A is the input array of numbers, N is the size of A.

int L[51];
int res=-1;
for(int i=0;i<N;i++)
{
 L[i]=1;
 for(int j=0;j<i;j++)
  if(A[j]<A[i])
  {
    L[i]=max(L[i],L[j]+1);
  }
 res=max(res,L[i]);
}
return res;

时间复杂度：O（N ² ）

这篇关于在最长递增Subquence荒诞条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！