数値配列を右にならした時の最大値

与えられた数値配列を右にならした時の最大値の求め方をまとめる。
ここで言う「右にならす」というのは、添字の小さい方から大きい方へのみ値を移動させて平均化する事を言う。例えば、a[0]=4, a[1]=2ならばa[0]=a[1]=3と平均化できるが、a[0]=2, a[1]=4である場合は値を移動できない…という操作のことである。


・方針

1. i = 1 からループを回し、i を上限にしてならせるかを調べる。
2. a[j] と i の差分を足しあわせていく。（sumとする）
3. sumがマイナス＝右から左にならす余地がある。→和を 0 にリセットする。
4. 最後にsum = 0なら i 以下にならすことができる。

3の解釈が難しいので図を添える。

これらのことをコードで実現すると以下のようになる。

int hoge(){
  int a[n];
  for(int i = 1; i <= MAX_A; i++){
    int sum = 0;
    for(int j = 0; j < n; j++){
      if(k + a[j] - i > 0) k += a[j] - i;
      else k = 0;
    }
    if(k == 0) return i;
  }
}

余談だが、6,7行目の条件分岐をなくして常に更新し、最後にk <= 0かをチェックすることによって自由にならすことが出来る場合の最大値を求めることもできる。ただ、あまりスマートな方法ではない。