6
\$\begingroup\$

This is the 26th exercise I solved from Codility. It scores 100%. I think I improved a lot since I started with this lessons, around 2 months ago, but still every post I made had things to be improved. What do you think about this code?

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:

class Solution { public int solution(int[] 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].

[PS: I'll upvote suggestions about sites that can help me get better at databases that follow a similar approach to codility]

using System;

class Solution {
    public int solution(int[] A) {
        var lastAddend = 0;
        var accumulator = 0 ; 
        var maxSliceSum = A.Length > 0 ? A[0] : 0 ;
        foreach(var addend in A)
        {
            var maxLastPair = Math.Max(addend, lastAddend + addend);
            accumulator = maxLastPair > accumulator + addend ? maxLastPair : accumulator + addend;
            maxSliceSum = Math.Max(maxSliceSum, accumulator);
            lastAddend = addend;
        }
        return maxSliceSum;
    }
}
\$\endgroup\$
  • \$\begingroup\$ More a review on the task: (P, Q) is not a pair of integers but a pair of indexes. This is dramatically different and liable to set people on the wrong foot. \$\endgroup\$ – Flater Nov 12 '19 at 13:13
  • 1
    \$\begingroup\$ @Flater That's a bit misleading. (P,Q) definitely is a pair of integers. And it is also a pair of indices. A better description would be to say it is a pair of integer indices. I really dont see the ambiguity the way you do. But I can imagine you see it. Nevertheless if you read this sentence: The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q]. then the ambiguity is gone. Anyway the task description is copied from the lesson in question, it is not work of the OP, so you can't really blame the OP for providing this slightly ambiguous description... \$\endgroup\$ – slepic Nov 12 '19 at 15:23
5
\$\begingroup\$

It might actualy be faster if you:

1) Avoid calling Math.Max if you can decide without evaluating the arguments (at least in some cases anyway).

2) Avoid repeating expressions.

3) Avoid writes when value is not changing.

using System;

class Solution {
    public int solution(int[] A) {
        var lastAddend = 0;
        var accumulator = 0 ; 
        var maxSliceSum = A.Length > 0 ? A[0] : 0 ;
        foreach(var addend in A)
        {
            // (1)+(2) var maxLastPair = Math.Max(addend, lastAddend + addend);
            // addend >= lastAdded + addend  ->  0 >= lastAddend
            var maxLastPair = 0 >= lastAddend ? addend : lastAddend + addend;
            // (2) accumulator = maxLastPair > accumulator + addend ? maxLastPair : accumulator + addend;
            accumulator = Math.Max(maxLastPair, accumulator + addend);
            // (3) maxSliceSum = Math.Max(maxSliceSum, accumulator);
            if (accumulator > maxSliceSum) maxSliceSum = accumulator;
            lastAddend = addend;
        }
        return maxSliceSum;
    }
}

EDIT:

This can actualy be optimized further:

Here you can see that addend is always component of maxLastPair:

var maxLastPair = 0 >= lastAddend ? addend : lastAddend + addend;

So let me split it:

var lastAddendIfPositive = lastAddend > 0 ? lastAddend : 0;
var maxLastPair = lastAddendIfPositive + addend;

Now let me replace the usage on the next line, and get rid of maxLastPair variable:

accumulator = Math.Max(lastAddendIfPositive + addend, accumulator + addend);

This is actualy the same as:

accumulator = Math.Max(lastAddendIfPositive, accumulator) + addend;

Now you see you save lastAddend to only use it if it is positive, so change the last loop line:

lastAddendIfPositive  = addend > 0 ? addend : 0;

And so you get rid of the first statement in the loop.

And we can actualy replace the Math.Max() with a conditional, as the function is so trivial that it is only meaningful as callback, otherwise it is just an unnecesary function call.

Now you can see that lastAddendIfPositive is only used if it is greater than accumulator and so we can get rid of this variable as well.

The final result looks like this:

class Solution {
    public int solution(int[] A) {
        var accumulator = 0 ; 
        var maxSliceSum = A.Length > 0 ? A[0] : 0 ;
        foreach(var addend in A)
        {
            accumulator += addend;
            if (accumulator > maxSliceSum) maxSliceSum = accumulator;
            if (addend > 0) {
              if (addend > accumulator) accumulator = addend;
            } else {
              if (accumulator < 0) accumulator = 0;
            }
        }
        return maxSliceSum;
    }
}

EDIT2: Btw im not sure about this line:

var maxSliceSum = A.Length > 0 ? A[0] : 0 ;

Your specification sais the input array is non empty. So you better throw exception if it is empty. Returning zero seems rather odd, because sum of empty set of values is rather undefined than it is zero.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Two minor remarks:

  1. For consistency sake, this

    accumulator = maxLastPair > accumulator + addend ? maxLastPair : accumulator + addend;
    

    can be implemented similar to the other statements as

    accumulator = Math.Max(maxLastPair, accumulator + addend);
    
  2. Some comments would be welcome in the loop. What exactly is the idea behind the different variables you keep. It took me a while to convince myself that your method was working as it should.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ That line you mention was written like that cause I couldn't get how the accumulator was supposed to handle 1 or 2 tests. So I did it as trial and error, until it worked, I should have tried to improve that line once it was working properly. Thanks! \$\endgroup\$ – newbie Nov 11 '19 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.