最长单调递增子序列之最优解法

元始天尊

今天看到2个题，
①设计一个O(n²)时间的算法，找出n个数组成的序列的最长单调递增子序列
②将①题算法时间改为O(nlogn)
这种题无非就是用动态规划或者直接遍历做了，直接遍历的话自然用2重循环搞定，时间 O(n²)
用动态规划则是用数组记录以a为结尾元素的最长递增子序列的长度，但是做法及其笨拙，他是这样写的：

1. int LISdyna()
   
2. {
   
3.         int i,j,k;
   
4.         for(i=1;b[0]=1;i<n;i++)
   
5.         {
   
6.                 for(j=0,k=0;j<i;j++)
   
7.                 {
   
8.                         if(a[j]<=a && k<b[j])
   
9.                         k=b[j];
   
10.                 }
    
11.                 b=k+1;
    
12.         }
    
13.         return maxL(n);
    
14. }
    
15. 
    
16. int maxL(int n)
    
17. {
    
18.         for(int i=0,temp=0;i<n;i++)
    
19.         {
    
20.                 if(b>temp)
    
21.                 temp=b;
    
22.         }
    
23.         return temp;
    
24. }

复制代码

经我改进，复杂度为O(n):

1. void func2(int* arr,int len)
   
2. {
   
3.         int* bn=new int[len];
   
4.         bn[0]=1;
   
5.         int i;
   
6.         for(i=1;i<len;i++)
   
7.         {
   
8.                 if(arr>arr[i-1])
   
9.                         bn=bn[i-1]+1;
   
10.                 else
    
11.                         bn=1;
    
12.         }
    
13.         int maxi=0;
    
14.         for(i=1;i<len;i++)
    
15.         {
    
16.                 if(bn>bn[maxi])
    
17.                 maxi=i;
    
18.         }
    
19.         cout<<endl<<"imin:"<<arr[maxi+1-bn[maxi]]<<" imax:"<<arr[maxi]<<endl;
    
20.         delete []bn;
    
21. }

复制代码

秋月孝三

为什么我没看懂呢？那个arr指针跟arr[i - 1]的比较是怎么回事？能帮忙写一下你测试的结果，ACM做了两年半，我第一次知道原来最长单增子序列有O（n）复杂度的？

元始天尊

秋月孝三 发表于 2014-4-14 22:51
为什么我没看懂呢？那个arr指针跟arr的比较是怎么回事？能帮忙写一下你测试的结果，ACM做了两年半，我第一 ...

网站bug   原本是 arr [ i ]