MaxDoubleSliceSum Codility Algorithm

Question

I stumbled upon this problem on Codility Lessons, here is the description:

A non-empty zero-indexed 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(vector &A);

that, given a non-empty zero-indexed 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.

Assume that:

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].

Complexity:

expected worst-case time complexity is O(N); expected worst-case space complexity is O(N), beyond input storage (not counting >the storage required for input arguments).

Elements of input arrays can be modified.

I have already read about the algorithm with counting MaxSum starting at index i and ending at index i, but I don't know why my approach sometimes gives bad results. The idea is to compute MaxSum ending at index i, ommiting the minimum value at range 0..i. And here is my code:

int solution(vector<int> &A) {
    int n = A.size();

    int end = 2;   

    int ret = 0;
    int sum = 0;

    int min = A[1];

    while (end < n-1)
    {
        if (A[end] < min)
        {
            sum = max(0, sum + min);
            ret = max(ret, sum);
            min = A[end];
            ++end;
            continue;
        }
        sum = max(0, sum + A[end]);
        ret = max(ret, sum);
        ++end;
    }

    return ret;
}

I would be glad if you could help me point out the loophole!

Answer 1

My solution based on bidirectional Kadane's algorithm. More details on my blog here. Scores 100/100.

public int solution(int[] A) {
  int N = A.length;
  int[] K1 = new int[N];
  int[] K2 = new int[N];

  for(int i = 1; i < N-1; i++){
    K1[i] = Math.max(K1[i-1] + A[i], 0);
  }
  for(int i = N-2; i > 0; i--){
    K2[i] = Math.max(K2[i+1]+A[i], 0);
  }

  int max = 0;

  for(int i = 1; i < N-1; i++){
    max = Math.max(max, K1[i-1]+K2[i+1]);
  }

  return max;
}