TopCoder SRM388 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について説明する。

厳密に増加する数列とは、前の数よりも大きい数字が続く数列である。厳密に減少する数列とは直前の数よりも小さい数字が続く数列である。厳密に単調な数列は厳密に増加する、もしくは厳密に減少するような数列を指す。例えば1, 5, 6, 10は厳密に増加する数列であり、1, 2, 2, 3は厳密に単調な数列ではない。seq[]という整数型の配列が与えられたとき、その部分列が厳密に単調になるもののうち、 最長になるものを求め、その長さを返すようなメソッドを作成せよ。

私の解答はこちら。

public class MonotoneSequence {

 public int longestMonotoneSequence(int[] seq) {
  int maxlen = 0; // 厳密に単調な数列の最大長
  int len = 0; // 現在見ている数列で連続に厳密に単調な数列が続いている長さ
  int prev = -1; // 直前の値
  // 厳密に増加する数列の中で最大の長さを計算
  for( int i=0 ; i<seq.length ; i++ ){
   if( seq[i] > prev ){
    len++;
    maxlen = Math.max(maxlen, len);
   }else{
    len = 1;
   }
   prev = seq[i];
  }
  System.out.println(maxlen);
  len = 0;
  prev = Integer.MAX_VALUE;
  // 厳密に減少する数列の中で最大の長さを計算
  for( int i=0 ; i<seq.length ; i++ ){
   if( seq[i] < prev ){
    len++;
    maxlen = Math.max(maxlen, len);
   }else{
    len = 1;
   }
   prev = seq[i];
  }
  return maxlen;
 }

}

得点は237.07/250、1回のsubmitでシステムテストクリア。中央値は約189点。