MaxDoubleSlice in Python and C++ Codility Solutions Lesson 9

This is the codility solution of the MaxDoubleSlice lesson 9, the algorithm is presented then solutions are written in Python and C++. A great practice exercise for online interviews and coding tests, usually carried out on Codility, Hackerrank, Leetcode, Projet Euler and so. Enjoy Practicing!

🍓 If you want to follow structured courses with more details and practice exercises check my "About" page for Discount Coupons on my Udemy courses covering: Python basics, Object Oriented Programming and Data Analysis with NumPy and Pandas, ... more courses are on the way drop me a message if you have a particular interesting topic! Good luck!

#python #cplusplusprogramming #codinginterview

[wonderjaxe]

These kinds of problems are just cruel. Even just understanding the problem is a monumental task.

[edwinmcc]

Thank you for taking time to explain it so clearly to dummies like me :) . .

[sammymishal]

You can do it in two loops instead of three, you can fill "LR" and "RL" in one loop ( as you fill LR[i] fill RL[n-1-i] ). or you can even use just one prefix sum with extra computation. BTW I love your videos.

[Dave-dley]

Thank you for making these videos, and thank you very much for breaking these down and explaining them into concepts that make sense that we can actually learn from :)

[frostman]

Thanks for all your help with thee videos, great stuff!

[Dimitris__]

When creating either the LR or the RL, and we come across a negative sum, isn't it more correct, to first set LR's or RL's value in the specific index as the actual negative sum that we got, before reseting s to 0? Because then in the last step, when we look for the maximum combination of slices, every point that would actually have a negative sum, is replaced with 0, which is wrong.

This example occures at 7:40 .

Sorry if I missed something, and what im saying is false.

Really appreciate your videos btw, they help me a ton!

[khadimali]

Just curious, @8:21 where you explained the correct configuration, shouldn't the Z index (highlighted by red background) be on -1 instead of 2? Please explain.

[音羽の夢]

When looping the LR and RL, you should start from the first index of LR, but your video just started it from the second index 6:30

[michaelx]

Thanks for sharing! But what happens if all the elements of array A is negative? Seems would return m=0

[dhmketu]

How to solve for the case where index 0 is included?

[tomfranky]

What's the output of your algorithm for the array [1, 2, 3, 4, 5, 6]?

[binhify]

I was banging my head against the wall asking what if the inputs are all negative number? and then I realized (3, 4, 5) has the sum of 0 so it doesn't really matter...

[doronb]

The solution principle is right, but I think the solution is wrong, along with Codility's behind-the-scene solution itself, and that is why this solution passes the test.

Your solution uses Kadane's algorithm on both sides of each "Y".
I believe this is wrong.
Kadane is taking the slice with maximum sum, while we on the left side (and a mirror on the right side) need the maximal sum of slices that *actually end* at that point.
In my own solution, I did use the principle of your solution of iterating on the "Y's" and checking the maximal sum on the left and on the right. But for the left and the right I did an intuitive and almost naive computation with same complexity.
Codility said my solution is wrong, and wrote:
"For example, for the input [0, 10, -5, -2, 0] the solution returned a wrong answer (got 8 expected 10) "