Maximum subarray problem - min value solution?

Question

Have you ever felt like your head wasn't meant for an algorithm?

I tried solving the maximum subarray problem and I came across this solution on Codewars:

var maxSequence = function(arr){
  var min = 0, ans = 0, i, sum = 0;
  for (i = 0; i < arr.length; ++i) {
    sum += arr[i];
    min = Math.min(sum, min);
    ans = Math.max(ans, sum - min);
  }
  return ans;
}

console.log(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, -4]));

I understand how to solve this problem with a linear time complexity using Kadane's algorithm:

var maxSequence = function(arr){
  let max = 0;
  let localMax = 0;

  for (let i = 0; i < arr.length; i++) {
    localMax = Math.max(localMax + arr[i], arr[i]);
    max = Math.max(localMax, max);
  }

  return max;
}

console.log(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, -4]));

But I can't make sense of why the first solution works. I simply can't grasp the idea behind it. I feel like a need a little help getting over the hump.

Edit: Here's a Codepen with some examples

Answer 1

The algorithm you provided is doing the same thing, in a more complex manner though. In order to explain it properly, I will compare the Codewars algorithm you provided with the Kadanes algorithm in various steps of their execution.

---

Let us consider the array:

[2 -4 3 2 6 -10 -12 20]

Here is the Codewars algorithm you provided:

var maxSequence = function(arr){
    var min = 0, ans = 0, i, sum = 0;
    for (i = 0; i < arr.length; ++i) {
        sum += arr[i];
        min = Math.min(sum, min);
        ans = Math.max(ans, sum - min);
    }
    return ans;
}

Here is the implementation of Kadanes algorithm mentioned in Wikipedia:

def max_subarray(numbers):
"""Find the largest sum of any contiguous subarray."""
best_sum = 0  # or: float('-inf')
current_sum = 0
for x in numbers:
    current_sum = max(0, current_sum + x)
    best_sum = max(best_sum, current_sum)
return best_sum

---

First step:-

sum changes to 2 and min remains the same. The ans changes to 2.

Second step:-

sum changes to -2 and min changes to -2. The ans is still 2. An interesting thing to notice here, according the implementation of Kadanes algorithm by Wikipedia, there in the second stage the value of current_sum will change to 0 which is the correct way to proceed.

However in the codewars implementation, the value of sum is still -2. If you notice a little more carefully though, you will observe that the value of sum-min is 0 in the codewars implementation. This is a really important point to notice. Instead of changing sum to 0 when its value reaches less than 0. We store the minimum number that must be substracted from sum to make the net sum 0. This value is stored in min and which also explains why it is named so.

Here is a record of the value of variables so far:

 sum    min    ans
  2      0      2     //ans = max(0, 2-0)
 -2     -2      2     //ans = max(2, -2+2)    

Third step:-

The sum changes to 1. min still remains the same. The ans changes to 3 which is the correct. How did this happen though?

In the Kadanes algorithm, you change the value of current_sum to 3 at this stage. In the codewars implementation, instead of changing sum to 3, what they have done is used a min variable which I repeat again stores the number that should be substracted from answer so that we obtain the same value as we do in current_sum. This is more clear from this part of the algorithm.

ans = Math.max(ans, sum - min);   //sum-min is current_max

Here when we substract the min from your sum. It neutralizes that extra negative in your answer. In this array A, the extra negative is 2 + (-4) = -2. In each of the following steps, we will observe that here sum is not containing the maximum continuous subarray sum. Maximum continuous subarray sum there is stored in sum - min. This is the key of this algorithm. sum-min is the current_sum here. Here are the following steps:

sum    min    ans
 1     -2      3      //ans = max(2, 1+2)
 3     -2      5      //ans = max(3, 3+2)
 9     -2      11     //ans = max(5, 9+2)
-1     -2      11     //ans = max(11, -1+2)

It is interesting to observe that even though the value of sum is negative in the last step, the value of min does not change. Why is that? The answer is it does not need to. If you look at sum-min is this case, it is 1 and not less than 0. Hence there is a possibility that if sufficient positive numbers follow after the current index in A, the value of sum-min might exceed the current value of ans. If you dry run Kadanes algorithm till this step, you will notice that even there the value of current_sum will not change to 0 at this stage, it will be 1.

Remaining steps:-

sum    min    ans
-1     -2      11     //ans = max(11, -1+2)
-13    -13     11     //ans = max(11, -13+13)
 7     -13     20     //ans = max(11,  7+13)

The most important point in this implementation, sum-min here is analogous to current_sum of Kadanes algorithm.

---

I should also mention that the Kadanes algorithm and codewars algorithm you provided will not work if the input array consists of all negative numbers. Both are not meant for it. There is a small implementation difference in the Kadanes algorithm if you want it to work for array consisting of all negative numbers (initialize current_sum to A[0]).

Do comment if you face any problems in understanding my explanation.

Answer 2

I don't think the the Codewars algorithm will work for every test case.

Following are the test cases where this algorithm will fail:

Test Case 1: arr = [-1]

Test Case 2: arr = [-1, -2]

For both the test cases, the algorithm under test gives an output equal to 0, which is not the correct answer.

PS: I have checked the Codewars problem. The test cases for the problem are not yet comprehensive and this problem has issues.

So for the time being, Kadane's algorithm is a good choice to solve the problem in linear time complexity.