最先增加的最长子序列然后减少

Question

我想解决以下问题:

---

元素值首先减少然后增加的序列称为V-序列.在有效的V序列中,在递增臂中应该至少有一个元素和至少一个元素.

例如,"5 3 1 9 17 23"是有效的V序列,其在减小臂中具有两个元素,即5和3,并且增加臂中的3个元素即9,17和23.但序列"6 4 2"或"8 10 15"中没有一个是V序列,因为"6 4 2"在增加部分中没有元素,而"8 10 15"在减少部分中没有元素.

通过从序列中删除零个或多个元素来获得序列的子序列.例如,定义"7","2 10","8 2 7 6","8 2 7 10 6"等是"8 2 7 10 6"的有效子序列.

给定N个序列的序列,找到其最长的子序列,即V序列.

---

我目前有一个O(n ^ 2)解决方案,其中我首先初始化一个数组(m []),使得每个m [i]包含在数组内'i'处开始的最长增长序列.

类似地,我初始化另一个数组(d []),使得每个d [i]包含该点处最长的递减序列ENDING.

这两个操作都需要O(n ^ 2)

我现在浏览这些数组并选择m [i] + d [i] -1的最大值,以满足所需的条件.

我想知道的是 - 是否有O(n lg n)解决方案？因为我的解决方案没有在规定的时间限制内运行.谢谢 :)

代码:

#include<cstdio>
#include<algorithm>

using namespace std;



int m[ 200000 ];
int d[200000 ];
int n;
int arr[200000 ];

void LIS()
{
    m[ n-1 ] = 1;

    int maxvPos = -1;
    int maxv = -1;

    for( int i=n-2; i>=0; i-- )
    {
        maxv = -1;
        for( int j=i+1; j<n; j++ )
        {
            if( ( m[j]+1 > maxv ) && ( arr[i] < arr[j]) )
            {
                maxv = m[j]+1;
                maxvPos = j;
            }


        }
        if( maxv>0 )
            {
                m[i] = maxv;
            }

            else
                m[i ] = 1;
    }

 }

void LDS()
{
      d[0] = 1;

    int maxv = -1;
    int maxvPos = -1;

    for( int i=1; i<n; i++ )
    {
        maxv = -1;
        for( int j=i-1; j>=0; j-- )
        {
            if( ( d[j]+1 > maxv) && arr[j]>arr[i] )
            {
                maxv = d[j]+1;
                maxvPos = j;
            }
        }

        if( maxv>0 )
            d[i] = maxv;

        else
            d[i]=1;
    }

}

int solve()
{
    LIS();
    LDS();

    int maxv = 0;
    int curr = 0;

    for( int i=0; i<n; i++ )
    {
        curr = d[i] + m[i] -1 ;

        if( ( d[i]>0) && (m[i]>0 ))
        {
            if( curr != 1 )
            maxv = max( curr, maxv );
        }

    }

    return maxv;

}

/*    static void printArr( int[] a )
{
    for( int i : a )
        System.out.print( i + " ");

    System.out.println();
} */


int main()
{
    scanf( "%d", &n );

    for( int i=0; i<n; i++ )
    {
        scanf("%d", &arr[i] );
    }   

    printf("%d\n", solve() );
    return 0;

}

Answer 1

有O(NlgK)最长增加子序列问题的算法,其中K是LIS长度.您可以查看Wikipedia以获取算法的描述.LightOJ也有一个很好的教程(这可能需要登录).