Straight Developer

Find a maximum sum of a compact subsequence of array elements.

In this article I am going to share with you a 100% score solution to the 3rd task of the Maximum slice problem lessons (chapter 9) on Codility.com, the solution has a O(n) time complexity and follows the same technique described in the chapter documentation pdf file (the last solution)
first, here’s the full task description from Codility.com:

Codility Max Slice Sum task description

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + … + A[Q].

Write a function:

function solution(A);

that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

For example, given array A such that:A[0] = 3 A[1] = 2 A[2] = -6 A[3] = 4 A[4] = 0

the function should return 5 because:

• (3, 4) is a slice of A that has sum 4,
• (2, 2) is a slice of A that has sum −6,
• (0, 1) is a slice of A that has sum 5,
• no other slice of A has sum greater than (0, 1).

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..1,000,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000];
• the result will be an integer within the range [−2,147,483,648..2,147,483,647].

get a 100% score on Max Slice Sum task with this solution

As I mentioned before, you can use the same technique as the one suggested by the chapter lesson document

 def golden_max_slice(A):
   max_ending = max_slice = 0
   for a in A:
     max_ending = max(0, max_ending + a)
     max_slice = max(max_slice, max_ending)
 return max_slice

however that won’t be enough because in case the array A contains only negative numbers then the result won’t be correct, for example:

A=[-1]

the function will return 0 while the right answer is -1 !

In order to take care of this exception all we need to do is to add a variable that keeps note of the highest number of the array while we iterate over each element, once the loop is done, if the max slice sum is equal to zero which is 99% when the array contains only negative values, in this case we return the highest number from the array instead of returning zero simply because the sum of two or more negative numbers will never be greater than the value of one them. Here’s the full solution :

function solution(A) {
    var sum=0
    var max=A[0]
    var maxCell=A[0]
    for(a of A){
        sum=Math.max(0,sum+a)
        max=Math.max(max,sum)
        maxCell=Math.max(maxCell,a)
    }
    if(max==0)
        return maxCell
    return max
}

I don’t think there exist a solution that will take less lines than this but if you think you can surprise me then don’t hesitate to do so by sharing your solution in the comments below !