[4,7,5,9,8]连续的串是[7,8,9]吧？

[ 本帖最后由 helloUJS 于 2013-4-9 13:06 编辑 ]

这题目简直无情，什么意思啊？

你好，题目的意思是求复杂度最小的程序吧。源代码写出来了，可是贴规不好意思发，发个算法应该可以把。
    for(i=0;i<N;i++)
    {
        if(a[i+1]>a[i])
        {
            if(j!=0&&j>b[1])
            {
                b[1]=j;
                j=1;
            }
            k++;
        }
        else
        {
            if(k!=0&&k>b[0])
            {
                b[0]=k;
                k=1;
            }
            j++;
        }
一个FOR循环搞定，算法也很小学生，呵呵。   a[]是输入数组  b[2]数组是存放正长度和逆长度的。
求给分啊。

题目描述不清楚
。。表示头大

有意思的命题，我想我看明白要求了。精确些描述大概是这样的

设有一个序列S(n)，含有n个互不相同的值，如果其子序列s(i,j)中（表示S序列中下标从i到j的元素）对于任意一个元素Ak(其中i<=k<=j)，都存在一个元素Ap（其中i<=p<=j）使得abs(Ak - Ap) = 1，则称这个子序列s(i,j)是连续的。换句话说，就是对s(i,j)重新排列后元素是整数连续就行。

问题，S(n)中最长的子序列的长度是多少？

设S中序列的范围是m，如果m不大的话（几百、几千、几万甚至百万量级），4楼小黑的想法是可取的，不过要更正一下，这样的时间复杂度不是O(n)，而是O(m)。

但如果m很大，则不能这么做。

O(n)的算法暂时没想到，容我想想，凭直觉觉得应该是存在的。

算法抛砖引玉吧，根据鸽笼原理可以得到这样一个结论：

设s(i,j)中的最大值为max，最小值为min，若max - min = j - i，则s(i,j)是连续的。