Lesson 7: MaxSliceSum (Max Slice Sum)

これもmax sliceのアルゴリズムです。

ただ、今回はOpen reading material (PDF) に書かれているアルゴリズムの前提と違って、

スライスのサイズが０にならない、必ず一つは要素が入るということになっています。

これにより、もしその位置で終わることのできるスライスの最大値がその、ポジションにある値より小さい場合、０の代わりにそのポジションの値をあらたなmax_endingとして採用しなければなりません。

以前０をつかっていたのは、値が小さくなる＝マイナスの値がそこに有る＝つまり何も取らないサイズ０のスライスをとるほうが値が０として扱えるので大きいという理由ですね。

ですから、今回はどうしても一つ値を取らなければ行けないので、上のような方針になるわけです。

これを実装してみると１００％のスコアがもらえました。

int solution(int A[], int N)
{   
    int max_ending = A[0];
    int max_slice  = A[0];

    int i;
   
    for (i = 1; i < N; i++){
        int tmp = max_ending + A[i];
        max_ending = tmp > A[i] ? tmp : A[i];
        max_slice  = max_slice < max_ending ? max_ending : max_slice;
    }
    
    return max_slice;
}