17 商湯筆試2

/*
* 題目描述： 求最長遞增序列
* 輸入 ：n 和n個整數
* 輸出 ： 整數n 代表最長遞增序列
* sample input : 3 1 6 5 
* sample output : 2 
* 思路： 對序列每一位置維護一個變量
* 表示目前位置最長序列長度，則每當多一個
* 數字的時候，該位置最長遞增序列，可以由
* 前面的小于該數的擁有最長遞增序列的遞增
* 序列長度加一獲得
**/

int main(){
	const int MAX_N = 1000;
	int n,ans;
	int a[MAX_N],f[MAX_N];
	cin >>n;
	for(int i = 0; i < n; ++i){
		cin>>a[i];
		f[i] = 1;
		for(int j = 0; j < i; j++){
			if((a[j]<a[i])&&(f[j]>=f[i]))
				f[i] = f[j] + 1;
		}
	}
	ans = 0;
	for(int i = 1; i < n; ++i){
		if(f[i] > ans) ans = f[i];
	}
	cout<<ans;
}