私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「【コロプラからの挑戦状！】バトルガールハイスクールで最大コンボをキメよう！」（CodeIQ）を参照してください。
【最大コンボを数えよう】
ランダムな整数値の並びがあります。
この中で、（左側）＜（右側）になっている数同士は「コンボが成立する」と言い、つながりがあるグループを作り、各グループのサイズをコンボ数とします。
たとえば、
(4, 5, 1, 2, 3)
という並びの場合、(4, 5) や (1, 2, 3) のようなグループができ、前者は2コンボ、後者は3コンボになります。
このようにコンボ数を調べるとき、最も大きなコンボ数がいくつになるかを答えてください。
【コンボの成立条件】
先の例のように完全に隣り合っている場合だけでなく、“1つまたは2つ”値を飛ばしてもコンボは成立します。
つまり、
(1, 2, 3, 5, 4, 5) のような並びの場合、(1, 2, 3, 5) の4コンボが最大ではなく、(1, 2, 3, 4, 5) の5コンボが最大になります。
(1, 2, 3, 5, 5, 4, 5) のような並びの場合も、(1, 2, 3, 4, 5) の5コンボが最大になります。
ただし、(1, 2, 3, 5, 5, 5, 4, 5) のような並びの場合、5が3つ並びコンボが途切れてしまうので、(1, 2, 3, 5) の4コンボが最大になります。
【入力】
1行目に正の整数値の数N(最大50)、2行目に正の整数値(100より小さい)がN個、半角スペース区切りで書かれています。
【出力】
最大コンボ数のみ出力してください。
【入出力サンプル】
Input
6
1 2 3 5 4 5
Output
5
Javaで解答しています。
import java.io.*;
public class Main{
/**
* 入力値を配列にパースする。
* 末尾に[0,0]をセンチネルとして追加する。
* @param line 入力文字列（数値列）
* @return 入力値を数値の配列に変換したもの
*/
public static int[] getInput(String line){
String[] s = line.split(" ", 0);
int[] ret = new int[line.length()+2];
for(int i=0; i<s.length; i++){
ret[i] = Integer.parseInt(s[i]);
}
return ret;
}
/**
* 3個先までチェックする
* @param last 現在のコンボの最後の数
* @param input 入力された数列
* @pos pos チェックする開始位置
* @return 次の値, 次の位置はいくつ進んだ場所か
*/
public static int[] checkNext3(int last, int[] input, int pos){
int nv = 100; // 次の値
int np = 0; // 次の位置
for(int i=0; i<3; i++){
if(last >= input[pos+i]) continue;
if(input[pos+i] <= nv){
nv = input[pos+i];
np = i+1;
}
}
int[] ret = {nv, np};
return ret;
}
/**
* sから始めた場合のコンボ数を返す
* @param input 入力された数列
* @param n inputの数
* @param s 先頭の位置
* @return コンボの数
*/
public static int getCombo(int[] input, int n, int s){
int last = input[s];
int ret = 1;
for(int i=s+1; i<n;){
int[] nxt = checkNext3(last, input, i);
last = nxt[0];
int mv = nxt[1];
if(mv == 0){
break;
}
else{
ret += 1;
i += mv;
}
}
return ret;
}
/**
* 問題を解く
* @param n 入力パラメータの数
* @param input 入力された数値列
* @return 最大のコンボ数
*/
public static int solve(int n, int[] input){
int max = 0;
for(int i=0; i<n; i++){
int cnt = getCombo(input, n, i);
if(cnt > max){
max = cnt;
}
}
return max;
}
/**
* メイン
*/
public static void main(String[] args) throws IOException {
try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
String line;
int n = 0;
int[] arr = null;
for(int i=0; (line = br.readLine()) != null; i++){
if(i == 0){
n = Integer.parseInt(line);
}
else if(i == 1){
arr = getInput(line);
}
}
int max = solve(n, arr);
System.out.printf("%d\n", max);
}
}
}
それほど難しい問題ではありません。
言語の選択が制限されていたので久しぶりにJavaにしました（Rubyで書いて投稿しようとしたらRubyが選択肢になかったので書き直しました）。
私のコードは単純です。
入力値の任意の場所からスタートし、常に2つ先までチェックしながらコンボが成立する値があればコンボが成立している場所まで進めてチェック、を繰り返すだけです。
コンボとして選択する値は現在の位置から2つ先までの値の中で、それまでに選択した値より大きく、かつ、3つの値の中で最小のものです。
また、同値の場合はより先にある方を選択します。
ちなみに、入力値の長さは最大で50に過ぎないので、この単純な方法でも計算量は最大でも1〜50の和に過ぎないためきにする必要はありません。
入力値の1行目を数値、2行目をgetInput()で数値の配列に変換します。
Javaなので1行目は無視しても良いのですが使いました。
入力値をsolve()に渡して結果を印字します。
入力値を数値の配列にします。
ちょっとした工夫が配列要素を2個増やして末尾を[0,0]にしていることです。
これによってチェック時に境界判定が不要になるのでコードがシンプルになります。
問題を解きます。
引数nは入力値の個数、inputは入力された数値列です。
inputの先頭から順に最後までを開始点としてgetCombo()に渡し、コンボ数を所得します。
変数maxがコンボ数の最大値で最大値が更新されるごとに書き換えます。
最後まで終わったらmaxに答えが記録されているので返却します。
inputの数値列に対し、s以上n以下の範囲でコンボ数を求めます。
変数lastはコンボに含まれる数値の中で最大の値を記録します。
変数retはコンボ数の値を記録します。retには先頭の値が必ず含まれているので初期値は1になります。
先頭の値は固定するのでs+1からnまでがコンボの探索範囲になります。
checkNext3()で2つ先までの値の中でコンボが成立する値を探します。checkNext3()は[コンボの値, 何個先の値か]を返すのでlastを返却値の最初の値、mvを返却値の2つ目の値で更新します。またコンボが成立しなかった場合、返却値の2つ目の値は0です。
なのでmvが0ならコンボが終了したということでブレークします。
そうでなければコンボ数をカウントアップし、インデックスカウンタをmvだけ増やして次のコンボをチェックします。
最終的にretをコンボ数として返却します。
inputの数字列に対してposから2つ先までの3個の値をチェックします。
その中でlastより大きく、最小の値をコンボを成立させる値として選択します（32〜39行目）。コンボを成立させる値に同値がある場合は後ろの方の値を選びます（35行目）。
コンボを成立させる値があった場合、nvをコンボの候補値、npをインデックスを進める数として記録します。
結果として[nv,np]の組みを返却します。
np=0の時は進める場所がない＝コンボ終了となります。