53607


[CodilityのMaxSliceSumという問題](https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_slice_sum/)  
[上記の問題を日本語で説明している記事](http://codility-lessons-
jp.blogspot.com/2015/03/lesson-7-maxslicesum.html)

を解き、コンパイルして評価したのですが、テストケース`A=[-10]`の時に`0ではなく-10`を返すように修正する必要がわかったため、変数の初期値に問題で指定されている想定されうる最も小さい値を入れるコードにしました。

しかし、変更後のコードでは他のバグが生じてしまい、修正方法がわかりません。

変更前のコードでは、テストケース`A=[3,2,-6,4,0]`の時に`5`が返されて要求を満たしています。

変更前

[code]

    def solution(A):
        maxsum = 0
        start = 0
        end = 0
        for i in range(len(A)):
            tmp = A[i]
            for j in range(i+1, len(A)):
                if tmp + A[j] > maxsum:
                    tmp = tmp + A[j]
                else:
                    break
    
            if tmp > maxsum:
                maxsum = tmp
    
        return (maxsum)
    
[/code]

しかしながら、変更後のコードでは`A=[3,2,-6,4,0]`の時に`4`が返されてしまうようになりました。

変更後

[code]

    def solution(A):
        maxsum = −2147483648 #変数maxsumの初期値を変更
        start = 0
        end = 0
        for i in range(len(A)):
            tmp = A[i]
            for j in range(i+1, len(A)):
                if tmp + A[j] > maxsum:
                    tmp = tmp + A[j]
                else:
                    break
    
            if tmp > maxsum:
                maxsum = tmp
    
        return (maxsum)
    
[/code]


CC BY-SA 4.0
2019-03-20T07:47:02.983
53582
2019-03-21T06:39:48.627
question
python python3 アルゴリズム
変数の初期値設定の変更が結果に与える影響


`A=[3,2,-6,4,0]`

2番目のforループで見てみましょう。

i==0, j==1のとき、`3+2 > maxsum (== -2147483648)` なので `tmp=5` になります。  
i==0, j==2のとき、`5+(-6) > maxsum`を比べます。それも正です！ だから`tmp=5+(-6)`になります。  
i==0, j==3のとき、`-1+4 > maxsum`  
i==0, j==4のとき、`3+0 > maxsum`

なので `i==0`の2番目のforループが終わった時に`maxsum = tmp(==3)`となります。

最終的に`i==3`のとき、`4+0 > maxsum (== 3)`なので `maxsum = 4` になります。

どうしましょうか？  
例えば以下のように2番目のループ内で`tmp`の最大値を`tmpmax`として保持しておくようにして修正することができそうです。

[code]

    def solution(A): 
         maxsum = -2147483648 
         for i in range(len(A)): 
             tmp = A[i] 
             tmpmax = tmp 
             for j in range(i+1, len(A)): 
                 tmp = tmp + A[j] 
                 if tmp > tmpmax: 
                     tmpmax = tmp 
    
             if tmpmax > maxsum: 
                 maxsum = tmpmax 
    
         return maxsum 
    
[/code]


CC BY-SA 4.0
2019-03-20T23:01:46.170
53607
2019-03-21T06:39:48.627
2019-03-21T06:39:48.627
3068
32617
53582
answer