数组中最长的升序子序列

我不是女神ヾ 2022-08-09 13:40 183阅读 0赞

2016喜马拉雅校园招聘笔试题？好像是，记不太清除了

属于 Dynamic programming 的范畴

[The longest Increasing Subsequence (LIS)][The longest Increasing Subsequence _LIS]  
给定一个序列，找到这个序列的一个最长的子序列，使得子序列的所有元素是升序的，且元素之间的相对位置不变（元素可以在原数组中不相邻，但是相对位置不变）  
比如, LIS for \{ 10, 22, 9, 33, 21, 50, 41, 60, 80 \} 是 6，LIS 是 \{10, 22, 33, 50, 60, 80\}.

**分析**  
arr\[0…n-1\]是输入，然后L(i)是到元素i为止 LIS 的长度，也就是arr\[i\]作为 LIS 的最后一个元素时 LIS 的长度，那么用递归形式 L(i) 可以写作：

for(j<i)
        if(arr[j]<arr[i]) L(i) = {1+Max( L(j) )} 
    if(j == 1) //递归的终止条件
        L(i) = 1

所以这个问题可以将其分解为 subproblems 用递归进行解决，

#include <iostream>
    using namespace std;
    
    int LIS(int *arr, int n, int *max_ref)
    {
      if(n==1) return 1;
      int res, longest_here=1;
    
      for(int i = 1; i<n; ++i)
      {
        res = LIS(arr, i, max_ref);
        if(arr[i-1]<arr[n-1] && res+1>longest_here)
          longest_here = res+1;
      }
    
      if(*max_ref < longest_here)
        *max_ref = longest_here;
    
      return longest_here;
    }
    
    int main()
    {
        int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
        int n = sizeof(arr)/sizeof(arr[0]);
        int max=1;
        LIS( arr, n, &max);
        cout<<max<<endl;
        return 0;
    }

非递归方法，这个需要开辟额外的存储空间。

int LIS2(int *arr,int n)
    {
      int *longest_here = new int[n]();
      longest_here[0] = 1;
      int max = 1;
      for(int i = 1; i<n; ++i)
      {
        for(int j = 0; j<i; ++j)
        {
          if(arr[j]<arr[i] && longest_here[j]+1>longest_here[i])
        longest_here[i] = longest_here[j]+1;
    
        }
        if(longest_here[i]>max)
          max = longest_here[i];
      }
    
      delete []longest_here;
      return max;
    
    }

wiki上边有时间复杂度为O(nlog(n))的[解法][Link 1]

[The longest Increasing Subsequence _LIS]: http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/
[Link 1]: https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms