The Max Slice Sum was a fun brain challenge.
I ended up finding the O(N) complexity solution after using the ol’ pen and paper trials.
So, I iterated over the array. At each step I calculated the maximum sum ending at the current element by comparing the minimum sum allowed, the current element, and the maximum previous ending + the current element.
The max slice is the maximum between the previous max slice and the maximum ending at the current place.
Solution in Javascript with O(N) complexity.
function solution(A) {
let minSum = 0-2147483648;
let maxSlice = minSum
let maxEnding = 0;
for (let i=0; i<A.length; i++){
maxEnding = Math.max(minSum, maxEnding+A[i], A[i])
maxSlice = Math.max(maxEnding, maxSlice)
}
if (maxSlice > 2147483647) {
maxSlice = 2147483647
}
return maxSlice
}
And here is the description and the algo report on Codility.