DouKaku?

数値のリストがあります。リストのサイズは N です。
ls[0]がリストの先頭要素、ls[N-1]が最後の要素です。

問題: 入力として与えられたリストが次の条件を満たすかどうかを求めてください。

for (int i = 0; i < N-1; i++) {
  ls[i] != ls[i+1] である
  ls[i] < ls[i+1] なら、ls[i] < ls[k] である(for all k = i+1 to N-1)
  ls[i] > ls[i+1] なら、ls[i] > ls[k] である(for all k = i+1 to N-1)
}

N の範囲は 3 <= N <= 50000 です。実行例を示します。

> check([1, 5, 4, 2])
True
> check([1, 2, 3])
True
> check([825, 102, 811, 140, 812, 125, 263])
False
> check([824, 102, 811, 140, 810, 155, 263])
True
> check([5, 4, 3, 2, 1])
True
> check([4, 2, 5, 3, 1])
False

JavaScript＠Firebugコンソールで。少し意訳しました。

>>> new Array(1,5,4,2).check();
true
>>> new Array(1,2,3).check();
true
>>> new Array(825,102,811,140,812,125,263).check();
false
>>> new Array(824,102,811,140,810,155,263).check();
true
>>> new Array(5,4,3,2,1).check();
true
>>> new Array(4,2,5,3,1).check();
false

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Array.prototype.check = function() {
  var upper = Number.MAX_VALUE;
  var lower = Number.MIN_VALUE;
  for (var i = 0; i < this.length; i++) {
    if ( (upper <= this[i]) || (this[i] <= lower) )
      return false;
    if (this[i] < this[i+1])
      lower = this[i];
    else
      upper = this[i];
  }
  return true;
};

ナイスツッコミ！
語感にやられました。（それをMIN_VALUEと言うか・・・。）
無限大に直してみました。

>>> new Array(0, 1, 2).check();
true

1
2
3
4
5

<  var upper = Number.MAX_VALUE;
<  var lower = Number.MIN_VALUE;
---
>  var upper = Number.POSITIVE_INFINITY;
>  var lower = Number.NEGATIVE_INFINITY;