algorithm - 如何确定一个序列是否是双调的？

Question

A sequence is bitonic if it monotonically increases and then monotonically de- creases, or if it can be circularly shifted to monotonically increase and then monotonically decrease. For example the sequences (1, 4, 6, 8, 3, −2) , (9, 2, −4, −10, −5) , and (1, 2, 3, 4) are bitonic, but (1, 3, 12, 4, 2, 10) is not bitonic.

如何确定给定的序列是否是双调的？

我有以下看法。我们可以走到n/2，其中n是数组的长度，然后检查是否

(a[i] < a[i + 1]) and (a[n - i - 1] < a[n-1 - (i + 1)])

这是正确的吗？

Answer 1

双调序列:

 /\
/  \
    \/

不是双调序列:

 /\    
/  \  / (higher than start)
    \/

显然，如果方向改变超过两次，我们就不能得到双调序列。
如果方向变化少于两次，我们必须有一个双调序列。

如果有两个方向变化，我们可能有一个双调序列。考虑上面的两个 ascii 图像。显然，具有两个方向变化的序列将匹配其中一个模式(允许反射)。因此，我们通过比较第一个和最后一个元素来设置初始方向。由于这些可以相同，因此我们使用不等于最后一个元素的第一个元素。

Java 中的实现:

    public static Boolean bitonic(int[] array) {
        if (array == null) return false;
        if (array.length < 4) return true;
        Boolean dir;// false is decreasing, true is increasing
        int pos = 0, switches = 0;
        while (pos < array.length) {
            if (array[pos] != array[array.length - 1])
                break;
            pos++;
        }
        if (pos == array.length) return true;
        //pos here is the first element that differs from the last
        dir = array[pos] > array[array.length - 1];
        while (pos < array.length - 1 && switches <= 2) {
            if ((array[pos + 1] != array[pos]) &&
               ((array[pos + 1] <= array[pos]) == dir)) {
                dir ^= true;
                switches++;
            }
            pos++;
        }
        return switches <= 2;
    }