Lesson 7: MaxDoubleSliceSum (Max Double Slice Sum)

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

This is yet another max slice problem.
The trick is to compute the maximum ending at each index for the left-side slice and the right-side slice first. Then, we move Y from 1 to N -2, scanning the max values for the left-side slice and the right-side slice at the index.

This strategy gives the 100% score.

#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;
}