I'm trying to find a solution to a codility question on minimum slice of a subarray, and I've devised a solution using a modified version of Kadane's algorithm. I've currently gotten 90/100 and managed to pass almost all the tests in O(n). However, I can't seem to pass "medium_range, increasing, decreasing (legth = ~100) and small functional, got 5 expected 3", and I have no idea why. This is possibly a repeat of solution, but I'm using a slightly different way of solving.
My logic is as follows:
a) if we have an array MinA where MinA[k] represents the minimum average slice of a subarray starting from k with minimum length of 2
b) then if we loop through MinA and find the minimum of the array, then this will be the minimum average slice for the whole array (and then return the index position)
c) to create this MinA, we start from the second last element of the array and MinA[A.length -2] is the average of the last two elements of A
d) we move the counter one position to the left; MinA[counter] will have to be either average of A[counter] and A[counter + 1] or the average of the elements counter and the elements in MinA[counter + 1]
e) if d was not true, then this implies that MinA[counter + 1] is not the minimal average slice from counter + 1 to some element from counter + 2 to N
I wonder if I'm missing something?
/*
* Using modified version of Kadane's algorithm
* The key logic is that for an array A of length N,
* if M[k + 1] is the minimum slice of a subarray from k + 1 to any element
* between k+2 to n, then M[k] is either the average of A[k] and A[k + 1], or
* the average of the elements k and the elements in M[k + 1]
*/
function solution(A) {
// you can use console.log for debugging purposes, i.e.
// console.log('this is debug message');
// write your code in JavaScript (ECMA-262, 5th edition)
var minSliceArray = [],
counter = A.length - 2,
currMinSliceLength = 0,
min = Number.POSITIVE_INFINITY,
minIndex = -1;
minSliceArray[counter] = (A[counter] + A[counter + 1]) / 2;
currMinSliceLength = 2;
counter--;
while (counter >= 0) {
var a = (A[counter] + A[counter + 1]) / 2,
b = (A[counter] + minSliceArray[counter + 1] * currMinSliceLength) / (currMinSliceLength + 1) ;
if (a < b) {
minSliceArray[counter] = a;
currMinSliceLength = 2;
} else {
minSliceArray[counter] = b;
currMinSliceLength++;
}
counter--;
}
//loops through the minSliceArray and find the minimum slice
for (var i = 0; i < minSliceArray.length; i++) {
if (minSliceArray[i] < min) {
min = minSliceArray[i];
minIndex = i;
}
}
return minIndex;
}