论坛 › 技巧探讨 › 最长单调递增子序列之最优解法

元始天尊 发表于 2014-2-13 23:57:43

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

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

int maxL(int n)
{
        for(int i=0,temp=0;i<n;i++)
        {
                if(b>temp)
                temp=b;
        }
        return temp;
}
经我改进，复杂度为O(n):void func2(int* arr,int len)
{
        int* bn=new int;
        bn=1;
        int i;
        for(i=1;i<len;i++)
        {
                if(arr>arr)
                        bn=bn+1;
                else
                        bn=1;
        }
        int maxi=0;
        for(i=1;i<len;i++)
        {
                if(bn>bn)
                maxi=i;
        }
        cout<<endl<<"imin:"<<arr]<<" imax:"<<arr<<endl;
        delete []bn;
}

秋月孝三 发表于 2014-4-14 22:51:18

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

元始天尊 发表于 2014-4-15 11:24:03

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

查看完整版本: 最长单调递增子序列之最优解法