Problem

A non-empty array A consisting of N integers is given.

A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.

The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].

For example, array A such that:

    A[0] = 3
    A[1] = 2
    A[2] = 6
    A[3] = -1
    A[4] = 4
    A[5] = 5
    A[6] = -1
    A[7] = 2

contains the following example double slices:

·         double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,

·         double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 - 1 = 16,

·        double slice (3, 4, 5), sum is 0.

The goal is to find the maximal sum of any double slice.

Write a function:

    int solution(int A[], int N); 

that, given a non-empty array A consisting of N integers, returns the maximal sum of any double slice.

For example, given:

     A[0] = 3
    A[1] = 2
    A[2] = 6
    A[3] = -1
    A[4] = 4
    A[5] = 5
    A[6] = -1
    A[7] = 2

the function should return 17, because no double slice of array A has a sum of greater than 17.

Write an efficient algorithm for the following assumptions: 

·         N is an integer within the range [3..100,000];

·        each element of array A is an integer within the range [-10,000..10,000].

Note:

The minimum length for the given array is 3.

From the definition of Maximum Double Slice Sum, it is clear that X=0 and Z=N-1 cannot be part of the summation, and so their values should be considered as 0, each 

A quotation from the question (problem) is, “The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].” From this, +A[Y] is deliberately omitted and its value should be considered as 0.

Demonstration

Example 1

Find the double slice sum of

    int A[] = {3, 2, 6, -1, 4, 5, -1, 2}; 

In the following table, the first row has the zero based indexes. The second row shows the special forward running sums of the given data with the first and second running sums made zero, each. The third row shows the special backward running sums of the given data with the last and last-but-one running sums made zero, each. The first and last values of the given data are not used in this algorithm. Each value in the fourth row is the vertical addition of the values in the two previous rows. The first three rows are not used in the algorithm, but have been put there so that the programmer does not confuse and use them instead of using the last three rows (see below).

The fourth row has the sum of the previous two rows, ignoring the first and last values. The fifth row shows the forward running sums of the given data where the first and second running sums are made zero, each. This differs from the second row above in that, when the running sum is negative (less than 0) it is replaced with 0. This 0 takes part in the continues special forward running sums. The sixth row shows the backward running sums of the given data where the last and last-but-one running sums are made zero, each. This differs from the third row above in that, when the running sum is negative (less than 0) it is replaced with 0. This 0 takes part in the continues special backward running sums. Each value in the seventh row is the vertical addition of the values in the two previous rows. These last three rows are what are used in the algorithm.

The highest value in the last row, is the double slice sum. Here, double slice sum is 17 at index Y=3. X=0 and Z=6.

Example 2

Find the double slice sum of

    int B[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

A table like the above is produced just below:

The highest value in the last row, is the double slice sum. Here, double slice sum is 7 at index Y=4. X=2 and Z=7.

Example 3

Find the double slice sum of

    int C[] = {-4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2};

A table like the above is produced just below:

The highest value in the last row, is the double slice sum. Here, double slice sum is 37 at index Y=5. X=0 and Z=15.

Algorithm for Smart Approach 

Smart Solution

#include <stdio.h>

int solution(int A[], int N) {

    int runSumF0[N]; 
    runSumF0[0]=0; 
    runSumF0[1]=0;
    for(int i=2;i<N;i++){
        int temp = runSumF0[i-1]+A[i-1];
        if (temp > 0)
            runSumF0[i] = temp;
        else
            runSumF0[i] = 0;
    }

    int runSumB0[N];
    runSumB0[N-1]=0;
    runSumB0[N-2]=0;
    for(int i=N-3;i>=0;i--){
        int temp = runSumB0[i+1]+A[i+1];
        if (temp > 0) 
            runSumB0[i]=temp;
        else
            runSumB0[i]=0;
    }
    
    int max_double=0;
    for(int i=1;i<N-1;i++){
        int temp = runSumF0[i] + runSumB0[i];
        if (temp > max_double)
             max_double=temp;
    }
    
    return max_double;
}

int main() 
{
        int A[] = {3, 2, 6, -1, 4, 5, -1, 2}; //double max 17 (X=0, Y=3, Z=6)
        int N = sizeof(A)/sizeof(A[0]);    //size of array divided by size of one (first) element
        int ret1 = solution(A, N);
        printf("%i\n", ret1);

        int B[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; //double max: 7 (X=2, Y=4, Z=6)
        N = sizeof(B)/sizeof(B[0]); 
        int ret2 = solution(B, N);
        printf("%i\n", ret2);
    
        int C[] = {-4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2}; //double max 37 (X=0, Y=5, Z=15)
        N = sizeof(C)/sizeof(C[0]); 
        int ret3 = solution(C, N);
        printf("%i\n", ret3);

    return 0; 
}

Comment