お題

整数がn個格納された配列(arr)が渡される(i.e. [3,-19,4,9,-9,3])
任意の連続した要素を取り出し最大値を求める。(i.e. 上記の場合は13となる。[4,9]の和)

自分が思いついた解法

・最初が負の値の場合、取り除きたいのでarr[0]からindexをインクリメントしていき、マイナスの値を除外し続ける。1以上の値が出現するまで繰り返す(ホントは全要素が負の数の場合を想定しないといけないが、今回は対象としない。)
　　i.e. [-2,-5,1,-4,9,3,-2,5] --> [1,-4,9,3,-2,5]

・arr[i] > 0 からiをインクリメントしていき、current_sumに連続した要素の和を代入し、max_sumにcurrent_sumの最大値を代入する

コード

イケてな解法のコード

# 色々駄目な部分が残っているので、真剣に読み解こうとすると時間の無駄になるので気をつけてください。
    i = 0
    while arr[i] <= 0:
        i += 1
        
    current_sum = 0
    max_sum = 0
    while i < len(arr):
        current_sum += arr[i]
        
        if current_sum > max_sum:
            max_sum = current_sum
            i += 1
            
            
        elif current_sum > 0:
            i += 1
            
            
        else:
            current_sum = 0
            i += 1
    
    
    return max_sum

イケてる解法

・コード見るだけで理解できるほど、スッキリしています。説明を書くよりコード見たほうが早いのですが、あえて説明すると、２つ変数を用意します。max_sumとcurrent_sumです。arr[0]を両方に代入します。初期値だと思ってください。
・indexを1からどんどんインクリメントしていきます。インクリメントする度に、arr[i]単体とcurrent_sumにarr[i]を足したもの、どちらか大きいものをcurrent_sumとします。次にcurrent_sumとmax_sumの大きいものをmax_sumとします。

コード

イケてる解法のコード

   max_sum = arr[0]
   current_sum = arr[0]

    for num in arr[1:]:
        #print("num is" + str(num))
        
        current_sum = max(current_sum + num, num)
        #print("current_sum is "+ str(current_sum))
        
        max_sum = max(current_sum, max_sum)
        #print("max_sum is "+ str(max_sum))
    return max_sum