動的計画4-最長増分サブシーケンス

一、問題:a[]={2,1,5,3,6,4,8,9,7}最長は5(1,3,4,8,9)二、問題分析:dp配列は1次元を設定し、1つの配列しかないためである.dp配列は,前j項の最大増分サブシーケンスの個数を格納する.現在の数が前の数より大きい場合は、前の数+1になります.△前の意味は、現在の数の前のすべてを意味します.三、状態転移方程式:

dp[i] = max(dp[i],dp[j] + 1)

ここで、iは現在の数字であり、jは0からiまでである.四、コード

#include
#define max(x,y) (x) > (y) ? (x) : (y)
int a[] = {
     2,1,5,3,6,4,8,9,7};
int n = sizeof(a) / sizeof(a[0]);
int dp[101];
int res = 0;//  
void solve()
{
     
	for(int i = 0; i < n; i++)
	{
     
		dp[i] = 1;//   ，    ，      1
		for(int j = 0; j < i; j++)
		{
     
			if(a[i] > a[j])//       
				dp[i] = max(dp[i],dp[j] + 1);//          +1    
			res = max(res, dp[i]);
		}
	}

	printf("%d
", res);
}
int main()
{
     
	solve();
	return 0;
}