Я пытаюсь решить следующий вопрос:
Последовательность, в которой значение элементов сначала уменьшается, а затем увеличивается, называется 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] содержит самую длинную убывающую последовательность, ЗАВЕРШАЮЩУЮСЯ в этой точке.
Обе эти операции занимают O( n^2 )
Теперь я просматриваю эти массивы и выбираю максимальное значение m[i] + d[i] -1 , такое, что требуемые условия выполняются.
Я хочу знать: существует ли решение O(nlgn)?? Потому что мое решение не работает в требуемые сроки. Спасибо :)
КОД:
#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;
}