POJ 2533 Longest Orderded Subsequence

Longest Increasing Sub-sequence(LIS)題目
想法：
    這裡提供兩種方法：

1. 把已經讀入的數字存起來，每次讀一個新的數字i的時候，就把LIS[i]設成1，然後把現在這個新數字i與以前已經讀入的數字j做比較，如果i比j大且LIS[i]<LIS[j]+1，就把LIS[i]=LIS[j]+1。最後輸出最大的LIS值即可。
2. 與上面不同，LIS[]是存讀入的數字，一開始LIS[]是空的，慢慢放數字，每次讀入一個新的數字，從i=0，如果該數字>LIS[i]，就讓i++，直到在LIS表裡上不去為止，然後看該數字是否比LIS[i]小，如果是則更新LIS[i]的値。

	#include <cstdio>
	using namespace std;
	// Method 1
	int main()
	{
	int N;
	scanf("%d", &N);
	int num[1001], LIS[1001];
	int Max = 0;
	for (int i = 0; i < N; ++i) {
	scanf("%d", &num[i]);
	LIS[i] = 1;
	for (int j = 0; j < i ; ++j) {
	if (num[i] > num[j] && LIS[i] < LIS[j]+1)
	LIS[i] = LIS[j]+1;
	}
	if (LIS[i] > Max) Max = LIS[i];
	}
	printf("%d\n", Max);
	}
	// Method 2
	int main()
	{
	int N, a;
	scanf("%d", &N);
	int LIS[1001], Max = 0;
	while (N--) {
	scanf("%d", &a);
	int i = 0;
	while (a > LIS[i] && i < Max) ++i;
	if (i == Max) {
	LIS[Max] = a;
	++Max;
	}
	else {
	if (a < LIS[i]) LIS[i] = a;
	}
	}
	printf("%d\n", Max);
	}

view raw [POJ] 2533 Longest Ordered Subsequence.cpp hosted with ❤ by GitHub