Lesson 7: MaxDoubleSliceSum (Max Double Slice Sum)

Lesson 7: MaxDoubleSliceSum
https://codility.com/programmers/lessons/7

また別のmax sliceの問題です。

この問題のポイントは、まず、それぞれのインデックスでおわる２つのスライス（左側からみてそこで終わるものと、右側から見てそこでおわるもの）の最大値を一度計算します。

その後Yの位置を1からN-2の間で動かして、左右のその位置でおわるスライスの合計値で最大のものを探せばOKです。

この方針で100%のスコアがもらえます。

#include <alloca.h>

int solution(int A[], int N) 
{
    if (N <= 3){
        return 0;
    }
    
    int* max_ending_l = (int*)alloca(sizeof(int) * N);
    int* max_ending_r = (int*)alloca(sizeof(int) * N);
     
    int i;
   
    //the max ending at the index from the left.
    max_ending_l[0] = 0;
    for (i = 1; i < N - 1; i++){
        int tmp = max_ending_l[i - 1] + A[i];
        max_ending_l[i] =  tmp < 0 ? 0 : tmp;
    }
    
    //the max ending at the index from the right.
    max_ending_r[N - 1] = 0;
    for (i = N - 2; i > 0; i--){
        int tmp = max_ending_r[i + 1] + A[i];
        max_ending_r[i] = tmp < 0 ? 0 : tmp;;
    }
    
    //then move Y to find the maximum double slice sum
    int max = 0;
    for (i = 1; i < N - 1; i++){
        int tmp = max_ending_l[i - 1] + max_ending_r[i + 1];
        if (max < tmp){
            max = tmp;
        }
    }
    
    return max;

}