最近嫂伞，在題目中穿仪，遇見了最長(zhǎng)不上升子序列的求解成榜，所以框舔，我特地思考了關(guān)于上升子序列的4中相關(guān)情況的求解。
最長(zhǎng)嚴(yán)格上升子序列
int LIS(int n)
{
int len = 1;
dp[1] = a[1];
for(int i=2; i<=n; ++i)
{
if(a[i] > dp[len])
{
dp[++len] = a[i];
}
else
{
int pos = lower_bound(dp, dp+len, a[i]) - dp;
dp[pos] = a[i];
}
}
return len;
}
最長(zhǎng)不嚴(yán)格上升子序列
int LIS(int n)
{
int len = 1;
dp[1] = a[1];
for(int i=2; i<=n; ++i)
{
if(a[i] > =dp[len])
{
dp[++len] = a[i];
}
else
{
int pos = upper_bound(dp, dp+len, a[i]) - dp;
dp[pos] = a[i];
}
}
return len;
}
最長(zhǎng)嚴(yán)格下降子序列
int LIS(int n)
{
int len = 1;
dp[1] = a[1];
for(int i=2; i<=n; ++i)
{
if(a[i] < dp[len])
{
dp[++len] = a[i];
}
else
{
int pos = lower_bound(dp, dp+len, a[i], greater<int>()) - dp;
dp[pos] = a[i];
}
}
return len;
}
最長(zhǎng)不嚴(yán)格下降子序列
int LIS(int n)
{
int len = 1;
dp[1] = a[1];
for(int i=2; i<=n; ++i)
{
if(a[i] <= dp[len])
{
dp[++len] = a[i];
}
else
{
int pos = upper_bound(dp, dp+len, a[i], greater<int>()) - dp;
dp[pos] = a[i];
}
}
return len;
}
