# 題目: UVa 10534 - Wavio Sequence

# 題目說明

給一個長度為 n 的整數序列，求此序列的 LIS 與 LDS 相連最長為多少

LIS 的結尾與 LDS 的開頭為同一個字
LIS 的長度與 LDS 相同

INPUT:
每筆測資輸入一個整數 n ，代表序列長度
接下來輸入 n 個整數

OUTPUT:
輸出相同長度且相連的最大 LIS 與 LDS 的合

若使用普通 DP 的方式找 LIS 與 LDS 會超時，所以使用 greedy algorithm 加速
分別找出 LIS 與 LDS 與每個元素的位置
( LDS 的找法為反向做 LIS )

之後設一個 t 從 LIS 與 LDS 中比較小的開始尋找
若 LIS 與 LDS 中的元素位置 num1[i] 與 num2[i] 皆不小於 t ，則跳出

輸出答案為 t * 2 - 1

更詳細關於 LIS 與 LDS 每個元素的位置
可以參考這篇

	#include <iostream>
	#include <vector>

	using namespace std;

	int main()
	{
	int n;

	while (cin >> n)
	{
	vector<int> str(n);
	for (int i = 0; i < n; ++i) cin >> str[i];

	vector<int> lis;
	vector<int> lds;
	lis.emplace_back(str[0]);
	lds.emplace_back(str[n - 1]);

	vector<int> num1(n);
	vector<int> num2(n);
	num1[0] = 1;
	num2[n - 1] = 1;
	int cnt1 = 1;
	int cnt2 = 1;

	for (int i = 1; i < n; ++i)
	{
	//lis
	if (str[i] > lis.back())
	{
	lis.emplace_back(str[i]);
	num1[i] = ++cnt1;
	}
	else
	{
	auto it = lower_bound(lis.begin(), lis.end(), str[i]);
	*it = str[i];
	num1[i] = (it - lis.begin() + 1);
	}

	//lds
	int j = n - i - 1;
	if (str[j] > lds.back())
	{
	lds.emplace_back(str[j]);
	num2[j] = ++cnt2;
	}
	else
	{
	auto it = lower_bound(lds.begin(), lds.end(), str[j]);
	*it = str[j];
	num2[j] = (it - lds.begin() + 1);
	}
	}

	int t = min(cnt1, cnt2);

	for (; t > 0; --t) for (int i = 0; i < n; ++i)
	if (num1[i] >= t && num2[i] >= t) goto out;

	out:
	cout << t * 2 - 1 << "\n";
	}
	}