急勾配の列の判定

急勾配の判定 - みずぴー日記からですが、元は急勾配の判定 DouKaku? からです。

有限の長さの数列で，各要素の値が，その要素の後ろにある残りの列に含まれる
すべての要素の和よりも大きい列を「急勾配の列」ということにします（空列の
和は0とします）．

任意の長さ（ただし有限の長さの）数列を与えられたとき，それが「急勾配の列」
であるかどうかを判定する述語関数を定義してください．

解き方ですが、この問題は配列の最初から計算するのではなく、最後から計算していく方が効率良く解くことができます。

#! /usr/bin/gawk -f
# super_inc.awk

BEGIN {

    arr[1] = 5; arr[2] = 4; arr[3] = 1;
    print is_super_inc(arr);

    arr[1] = 5; arr[2] = 2; arr[3] = 1;
    print is_super_inc(arr);

}

# is_super_inc():   急勾配かどうかを判定する
#   in:     配列 arr
#   out:    急勾配の場合 1、そうでない場合 0 を返す
function is_super_inc(arr,     i, num_arr, sum_left) {
    for (i in arr) {
        num_arr++;
    }

    for (i = num_arr; i >= 1; i--) {
        if (arr[i] <= sum_left) {
            return 0;
        }
        sum_left += arr[i];
    }
    return 1;
}

BEGIN ブロックにある最初のものは 0 を返し、後のものは 1 を返します。 実際に実行してみましょう。

$ nawk -f super_inc.awk
0
1

ここでは nawk などでも動作するように配列の数を for 〜 in で数えていますが、もちろん gawk であれば length(arr) で計数することができます。 特に効率は考えていませんが、この場合の O-記法での表記は O(n) になります。