https://vn.spoj.com/problems/SPSEQ
https://oj.vnoi.info/problem/SPSEQ
W. là 1 dãy các số nguyên dương. Nó có các đặc điểm sau:
Ví dụ: 1, 2, 3, 4, 5, 4, 3, 2, 1 là 1 dãy W. độ dài 9. Tuy nhiên, dãy 1, 2, 3, 4, 5, 4, 3, 2, 2 không là 1 dãy W.
Yêu cầu: Trong các dãy con của dãy số cho trước, tìm dãy W. có độ dài dài nhất.
Dòng 1: số nguyên dương N (N <= 100000), độ dài dãy số.
Dòng 2: N số nguyên dương ai (ai <= 10^9).
1 số nguyên dương duy nhất là độ dài dãy W. dài nhất.
Input
10
1 2 3 4 5 4 3 2 1 10
Output
9
Input
19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1
Output
9
Bài này đơn giản chỉ là tìm dãy con tăng dài nhất từ 1 -> i với mỗi 1 <= i <= n và dãy con giảm dài nhất tử i -> n với mỗi 1 <= i <= n. (thực chất chỉ là duyệt dãy từ n -> 1 tìm dãy tăng dài nhất). Kết quả là
Max(2 * min(F[0][i]-1, F[1][i]-1) + 1) với mỗi 1 <= i <= n.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef unsigned long long ull;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define ep emplace_back
#define EL printf("\n")
#define sz(A) (int) A.size()
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FOD(i,r,l) for (int i=r;i>=l;i--)
#define fillchar(a,x) memset(a, x, sizeof (a))
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int N = 1e5+5;
int n, a[N], f[N], g[N], s[N], maxL;
int LIS(int i) {
int l = 1, r = maxL, j = 0;
while (l <= r) {
int m = (l+r)/2;
if (a[i] > a[s[m]]) {
j = m;
l = m+1;
} else r = m-1;
}
if (j == maxL) s[++maxL] = i;
if (a[i] < a[s[j+1]]) s[j+1] = i;
return j;
}
int main() {
// freopen("INP.TXT", "r", stdin);
// freopen("OUT.TXT", "w", stdout);
cin >> n;
FOR(i,1,n) scanf("%d", &a[i]);
f[1] = 1;
s[1] = 1;
maxL = 1;
FOR(i,2,n) {
int j = LIS(i);
f[i] = j+1;
}
g[1] = 1;
s[1] = n;
maxL = 1;
FOD(i,n-1,1) {
int j = LIS(i);
g[i] = j+1;
}
int res = 0;
FOR(i,1,n)
res = max(res, 2*min(f[i], g[i]) - 1);
cout << res << endl;
return 0;
}