UVa 10534 Wavio Sequence

Longest Increased/Decreased Subsequence
想法：
    替數列建LIS和LDS表，然後在從表中找出共同最大的數字。例如：
數列： 1 2 3 4 5 3 2
LIS：  0 1 2 3 4 0 0
LDS：  0 0 0 0 2 1 0
因此數字'5'的LIS為4,LDS為2，所以'5'為中心組成Wavio Sequence的長度就是min(4,2)*2+1=5。因此本題就從LIS和LDS表中找出最長的Wavio Seq長度。
    至於求LDS我是由後面往前作LIS，因此這題就是做兩次LIS，另外要注意如果用O(n^2)演算法可能會TLE。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N;
	int num[100001];
	int LIS[100001]; //LIS的Stack
	int lis[100001]; //每個數字LIS的表
	int LDS[100001];
	int lds[100001];
	int LIS_Max, LDS_Max; // 表示LIS的Stack有幾層(level)
	void LIS_function(int i);
	void LDS_function(int i);
	int main()
	{
	// freopen("input.txt", "rt", stdin);
	while (scanf("%d", &N) != EOF) {
	LIS_Max = 0, LDS_Max = 0;
	for (int i = 0; i < N; ++i)
	scanf("%d", &num[i]);
	for (int i = 0, j = N - 1; i < N; ++i, --j) {
	LIS_function(i);
	LDS_function(j);
	}
	int Max = 0;
	for (int i = 0; i < N; ++i)
	if (min(lis[i], lds[i]) > Max)
	Max = min(lis[i], lds[i]);
	printf("%d\n", 2 * Max + 1);
	}
	}
	void LIS_function(int i)
	{
	int j = 0;
	while (num[i] > LIS[j] && j < LIS_Max) ++j;
	if (j == LIS_Max) {
	LIS[LIS_Max] = num[i];
	++LIS_Max;
	}
	else if (num[i] < LIS[j])
	LIS[j] = num[i];
	lis[i] = j;
	}
	void LDS_function(int i)
	{
	int j = 0;
	while (num[i] > LDS[j] && j < LDS_Max) ++j;
	if (j == LDS_Max) {
	LDS[LDS_Max] = num[i];
	++LDS_Max;
	}
	else if (num[i] < LDS[j])
	LDS[j] = num[i];
	lds[i] = j;
	}

view raw [UVa] 10534 Wavio Sequence.cpp hosted with ❤ by GitHub