Longest subsequence that first increases then decreases

Question

I am trying to solve the following question :

---

A sequence in which the value of elements first decrease and then increase is called V- Sequence. In a valid V-Sequence there should be at least one element in the decreasing and at least one element in the increasing arm.

For example, "5 3 1 9 17 23" is a valid V-Sequence having two elements in the decreasing arm namely 5 and 3, and 3 elements in the increasing arm namely 9, 17 and 23 . But none of the sequence "6 4 2" or "8 10 15" are V-Sequence since "6 4 2" has no element in the increasing part while "8 10 15" has no element in the decreasing part.

A sub-sequence of a sequence is obtained by deleting zero or more elements from the sequence. For example definition "7", "2 10", "8 2 7 6", "8 2 7 10 6" etc are valid sub-sequences of "8 2 7 10 6"

Given a sequence of N numbers find its longest sub-sequence which is a V-Sequence.

---

I currently have an O( n^2 ) solution wherein I first initialize an array ( m[] ) such that each m[i] contains the longest increasing sequences STARTING at 'i' within the array.

Similarly, I initialize another array ( d[] ), such that each d[i] contains the longest decreasing sequence ENDING at that point.

Both of these operations take O( n^2 )

I now go through these arrays and choose the maximum value of m[i] + d[i] -1 , such that required conditions are satisfied.

What I want to know is - Is there an O( n lg n ) solution ?? Because my solution does not run within required time limits. Thank you :)

CODE :

#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

There are O(NlgK) algorithm for Longest Increasing Subsequence problem, where K is the LIS length. You can check Wikipedia for a description of the algorithm. LightOJ also has a nice tutorial (this might require login).