我正在尝试解决以下问题:
元素值先减小后增大的序列称为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 ) 解决方案?因为我的解决方案没有在规定的时间限制内运行。谢谢 :)
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;
}