Search code examples
arraysalgorithmkadanes-algorithm

Solving MaxDouble Slice Kadane's Algorithm Variation

I was trying to sharpen my skills by solving the Codality problems. I reached this one: https://codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

I actually theoretically understand the solution:

  1. Use Kadane's Algorithm on the array and store the sum at every index.
  2. Reverse the array and do the same.
  3. Find a point where the sum of both is max by looping over both result sets one at a time.
  4. The max is the max double slice.

My question is not so much about how to solve the problem. My question is about how does one imagine that this will be way in which this problem can be solved. There are at-least 3 different concepts that need to be made use of:

  1. The understanding that if all elements in the array are positive, or negative it is a different case than when there are some positive and negative elements in the array.

  2. Kadane's Algorithm

  3. Going over the array forward and reversed.

Despite all of this, Codality has tagged this problem as "Painless".

My questions is am I missing something? It seems hard that I would be able to solve this problem without knowing some of these concepts.

Is there a technique where I can start from scratch and very basic concepts and work my way up to the concepts required to solve this problem. Or is it that I am expected to know these concepts before even starting the problem?

How can I prepare my self to solve such problems where I don't know the required concepts in the future?

Solution

  • I think you are overthinking the problem, that's why you find it more difficult than it is:

    The understanding that if all elements in the array are positive, or negative it is a different case than when there are some positive and negative elements in the array.

    It doesn't have to be a different case. You might be able to come up with an algorithm that doesn't care about this distinction and works anyway.

    You don't need to start by understanding this distinction, so don't think about it until or even if you have to.

    Kadane's Algorithm

    Don't think of an algorithm, think of what the problem requires. Usually that 10+ paragraph problem statement can be expressed in much less.

    So let's see how we can simplify the problem statement.

    It first defines a slice as a triplet (x, y, z). It's defined at the sum of elements starting at x+1, ending at z-1 and not containing y.

    Then it asks for the maximum sum slice. If we need the maximum slice, do we need x and z in the definition? We might as well let it start and end anywhere as long as it gets us the maximum sum, no?

    So redefine a slice as a subset of the array that starts anywhere, goes up to some y-1, continues from y+1 and ends anywhere. Much simpler, isn't it?

    Now you need the maximum such slice.

    Now you might be thinking that you need, for each y, the maximum sum subarray that starts at y+1 and the maximum sum subarray that ends at y-1. If you can find these, you can update a global max for each y.

    So how do you do this? This should now point you towards Kadane's algorithm, which does half of what you want: it computes the maximum sum subarray ending at some x. So if you compute it from both sides, for each y, you just have to find:

    kadane(y - 1) + kadane_reverse(y + 1)

    And compare with a global max.

    No special cases for negatives and positives. No thinking "Kadane's!" as soon as you see the problem.

    The idea is to simplify the requirement as much as possible without changing its meaning. Then you use your algorithmic and deductive skills to reach a solution. These skills are honed with time and experience.