# 題目: UVa 10534 - Wavio Sequence

# 題目說明

給一個長度為n的整數序列，求此序列的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

# 參考程式碼

#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";
	}
}