Codilityテスト：昇順が最も長く続く部分を調べる問題

とあるスイスのIT企業のバイトの入社試験で，「Codility」というOnlineテストを受けさせられた．自分にとってははじめての存在だったので念のためシェア．

事前に調べるとこういう感じの問題みたい．ちょっと頭を使うことを覚悟する．
http://tjnet555.hatenablog.com/entry/2016/09/03/191251

アルゴリズムの知識で計算量を減らさないと得点が低くなるらしい．
デモで $O(n^2)$ の式を書いたら，Correctnessは100%だったが，Efficiencyみたいなのが25%だった．
なるほどなと思い本番へ．

自分の場合は，

• 試験時間は45分
• タスクは1問
• Pythonで受けろと会社から指定．

問題文は英語で，20行ぐらい．最初の5分ぐらいで何が言いたいのか理解できた．

問題はこんな感じ
ーーーーーーーーーーーーーーー
[2, 2, 2, 2, 1, 2, -1, 2, 1, 3]といったようなリストがあった時に，昇順になっている部分で最も長い部分を探し，その部分の始まりのインデックスを返す関数solution(A)を作成する．
上の例だと，4か6か8のどれかを返せばいい．

[30, 20, 10]だと，0か1か2 (ひとつの数字は長さ1の昇順の部分と考える)
配列の長さNは1<=N<=150,000，
Aに含まれる整数Kの範囲は，-(2^31)<=K<=(2^31)
ーーーーーーーーーーーーーーー

書いたコードを下に示した．
$O(n)$で計算量は，色々工夫はできるけど，オーダーはこれ以上減らせなくないですか...?
大学生バイトだから，初歩的な問題にしてくれたみたいです．

def solution(A):
    max = 0
    begin = 0
    target = 1
    length = 1
    max_length = 1
    list_length = len(A)
    while target < list_length:
        if (A[target - 1] < A[target]):
            length = length + 1
        else:
            if length > max_length:
                max = begin
                max_length = length
            begin = target
            length = 1
        target = target + 1
    if length > max_length:
        max = begin
        max_length = length
        return max