C++最長降下サブシーケンス問題について
2447 ワード
/* O(n^2) */
#include <iostream>
using namespace std;
int main()
{
int m,i,j; // m
int hig[20],sco[20]; // hig[20]
// sco[20]
// .
cin>>m;
for( i = 0; i < m; ++i )
cin>>hig[i];
sco[0] = 1; // 1
for( i = 1; i < m; ++i )
{
sco[i] = 1; //
for( j = 0; j < i; ++j )
{
// hig[i] < hig[j] '<' '>'
// 。
// 。
if(hig[i]<hig[j] && sco[j]+1>sco[i])
sco[i] = sco[j]+1;
}
}
int max = 0;
for( i = 0; i < m; ++i ) //
if(sco[i] > max)
max = sco[i];
cout<<max<<endl; //
return 0;
}
// : ( ) ?