Wiki OI 1044迎撃ミサイル

タイトルリンク:http://wikioi.com/problem/1044/
アルゴリズムと構想:
問題の意味をよく理解すると、実際には最長上昇サブシーケンスと最長下降サブシーケンスを求めます.
シーケンス全体を順次巡回し、最初の数から現在の数までの最長上昇サブシーケンスを求めるたびに、
最後の数字まで遍歴し、dp配列の中で最大のそれがシーケンス全体の最長上昇サブシーケンスである.
シーケンス1−iの最長上昇サブシーケンスの長さをdp[i]=max(dp[j])+1,(j∈[1,i−1])で格納する. 
明らかにdp[1]=1であり,i=2から後の要素を遍歴すればよい.

#include<stdio.h>
#include<string.h>
int n = 0, dp1[100005], dp2[100005];
int a[100005];
int DP1(int len)
{
	int i, j, ans = 1, Max = 0;
	dp1[1] = 1;
	for(i = 2; i <= len; i++)
	{
		Max = 0;
		for(j = 1; j < i; j++)
		{
			if(dp1[j] > Max && a[j] > a[i])
			    Max = dp1[j];
		}
		dp1[i] = Max + 1;
		if(dp1[i] > ans)
		     ans = dp1[i];
	}
	return ans;
}
int DP2(int len)
{
	int i, j, ans = 1, Max = 0;
	dp2[1] = 1;
	for(i = 2; i <= len; i++)
	{
		Max = 0;
		for(j = 1; j < i; j++)
		{
			if(dp2[j] > Max && a[j] < a[i])
			    Max = dp2[j];
		}
		dp2[i] = Max + 1;
		if(dp2[i] > ans)
		     ans = dp2[i];
	}
	return ans;
}
int main()
{
	while(scanf("%d", &a[++n]) != EOF);
	printf("%d
", DP1(n - 1));
	printf("%d
", DP2(n - 1));
	return 0;
}