SRM585 Div2 Easy "LISNumberDivTwo"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12446
訳
A を整数のシーケンスとする。我々はいくつかの(1以上の)増加列の連結したものとして、シーケンスを作成したい。AのLISNumberとは増加列の最小の数のことである。
例えば、A = {1, 4, 4, 2, 6, 3}のLISNumberは4である。なぜならAは{1, 4} + {4} + {2, 6} + {3}として作成でき、3つの(それより小さい)増加列を連結ではAを作成する事はできないからである。
他の例として、B = {10, 20, 30}のLISNumberは1である。なぜならBはすでに増加列だからである。
あなたにはint[] seqが与えられる。seqのLISNumberを返せ。
制約
1 <= seqの要素数 <= 50
考えた事
貪欲になるべく長い増加列を作っていく
ソースコード
class LISNumberDivTwo { public: int calculate(vector <int> seq){ int n = seq.size(); int ans = 1; int p = 0; for( int i = 0; i < n; i++ ){ if( seq[i] <= p ) ans++; p = seq[i]; } return ans; } };