最长子是先增加再减少 [英] Longest subsequence that first increases then decreases
问题描述
我试图解决以下问题：
一个序列中的元素首先减少的值，然后增加被称为V-序列。在一个有效的V-序列应该有向上升臂下降和至少一个元素的至少一种元素。
例如，5 3 1 9 17 23是具有在减少臂即5和3中增加臂即9，17及23的两个元素，和3个元素的有效的V-序列。但没有序列6 4 2或8 10 15的垂直序列，因为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]包含最长递增序列开始'我'在阵列中。
类似地，我初始化另一个阵列（D []），使得各d [I]包含最长递减序列ENDING在这一点上。
这两种方法需要为O（n ^ 2）
我现在通过这些阵列，并选择m的最大值[I] + D [I] -1，使得所需要的条件得到满足。
我想知道的是 - 是否有一个O（N LG N）解决方案？因为我的解决方案不要求在时间限制运行。谢谢：）
code：
＃包括＆LT; cstdio＆GT;
＃包括＆LT;算法＆GT;
使用名字空间std;
INT M [200000]。
INT D [200000]。
INT N;
INT ARR [200000]。
无效LIS（）
{
米[N-1] = 1;
INT maxvPos = -1;
INT MAXV = -1;
的for（int i = N-2; I＆GT; = 0;我 - ）
{
MAXV = -1;
为（诠释J = i + 1的; J＆n种; J ++）
{
如果（（M [J] +1＆GT; MAXV）及及（ARR [1] - ，常用3 [J]））
{
MAXV = M [J] +1;
maxvPos = j的;
}
}
如果（MAXV大于0）
{
M [] = MAXV;
}
其他
米[I] = 1;
}
}
无效LDS（）
{
D [0] = 1;
INT MAXV = -1;
INT maxvPos = -1;
的for（int i = 1;我n种;我++）
{
MAXV = -1;
对于（INT J = I-1; J＆GT; = 0; j--）
{
如果（（D [J] +1＆GT; MAXV）及和放大器;常用3 [J] GT;常用3 [I]）
{
MAXV = D [J] +1;
maxvPos = j的;
}
}
如果（MAXV大于0）
D [i] = MAXV;
其他
D [I] = 1;
}
}
INT解决（）
{
LIS（）;
LDS（）;
INT MAXV = 0;
INT CURR = 0;
的for（int i = 0;我n种;我++）
{
CURR = D [I] + M [] -1;
如果（（四[I] 0）＆安培;及（米[I]＆0））
{
如果（CURR！= 1）
MAXV = MAX（CURR，MAXV）;
}
}
返回MAXV;
}
/ *静态无效printArr（INT []一）
{
对于（INT I：1）
System.out.print第（i +）;
的System.out.println（）;
} * /
诠释的main（）
{
scanf函数（％d个，和放大器; N）;
的for（int i = 0;我n种;我++）
{
scanf函数（％d个，和放大器;常用3 [I]）;
}
的printf（％D \ N，解决了（））;
返回0;
}
有 O（NlgK）算法最长递增序列问题，其中氏/ code>是LIS的长度。您可以检查维基百科，在算法的描述。 LightOJ 也有一个很好的教程（这可能需要登录）。
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;
}
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).
这篇关于最长子是先增加再减少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
