概要
数列が与えられる。
この数列が最小でいくつの狭義単調増加列に分割されるか求めよ。
解法
隣接する要素が狭義単調増加でないとき、必ずその場所で分割する必要があります。
それ以外の場合分割する必要はありません。
従って、全ての隣り合う二要素について、狭義単調増加でないようなものの数が答えになります。
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) class LISNumberDivTwo { public: int calculate( vector <int> seq ) { int res = 1; REP( i, 0, seq.size() - 1 ) { res += seq[i] >= seq[ i + 1 ]; } return res; } };
