Calvin’s Game INOI problem fully explained with solution (EDITORIAL) (1D — DP)
You are given an array a of length N. You start at position k. In the forward phase, you make jumps of size 1 or 2 towards the right. Then in the backward phase, you make jumps of size 1 of 2 towards the left till you reach position 1. Your score is the sum of the values in the array where you landed after each jump. What is the maximum score you can make?
Explanation:
Before starting reading the explanation I would suggest you to click on the problem link and read the full problem.
Cool, so let’s get started.
So , programmatically we can consider this as an 1-D array with index from 1 to N where each index represent a square.
Throughout the problem assume 1 based indexing.
From index K you can move forward 0 or more steps, and then you have to reach index 1 by taking backward step(s). Since we have to take the maximum sum possible so we have to choose the array elements in an optimal manner. The first thing that comes to our mind is to take all the positive numbers and skip the negative numbers.
Let’s say our array consists of 2 3 -5 7 -8 and we start from index 1. Therefore I will jump to index 2 ,then index 4 then come back to index 2 again finishing at index 1. Thus we get the sum 15 (3+7+3+2) which is the maximum sum possible.
But lets say we have an array 2 3 -5 -1 8 and start from index 1. Is it possible to take ONLY positive numbers? Yes obviously but in this case you will go to index 2 and and then come back to index 1 with sum = 5. But I can give you a greater sum. I will go to index 2 and then index 4 then index 5 come back to index 4, index 2 and eventually index 1 with a sum 14. So always taking ONLY positive number’s wont help. You can also assume a case where there are negative numbers only. So it seems that this approach won’t help.
So? Seems like there is no greedy solution to this and we have to try out each and every combination of choosing each step.
So at every step we have 4 options, either to go 1 step ahead or 2 steps ahead. We can also go 1 step back or 2 steps back, but once we start going backwards we cant move forward anymore.
So let’s break down this problem into 2 parts.
Let’s find out that if we go forward from index ‘K’ what is the maximum sum possible to reach an index ‘i’ and also what is the maximum sum we can achieve in going back from index ‘i’ to 1.
For example say an array 5 3 -2 1 -1 and we start from index 1. So the maximum sum we can achieve starting from 1 is 4 and we end at index 4. So we will add 4 to maximum sum achieved if we go backwards from position 4.
So we will first think about the forward solution.
So at every point we have two choices, go 1 step ahead or go 2 steps ahead (obviously keeping the boundary in mind). and while choosing the current step out of these 2 options, I will take that step having maximum sum from these 2 steps.
We can sense we will need recursion, because we have to check for all possible combinations. But recursion will not pass all the test cases therefore we need to optimise it.
Now let’s see how can we do that.
Suppose I start from index 1 and go to index 2,3,4 updating the sum. From 4 we calculate the maximum sum that can be achieved if we go backwards from 4 to 1 and add that to our forward sum from index 1 to index 4 . Now for the same array if we try another combination say , we start from index 1 and go to index 3 then index 4(skipping index 2 this time), then again from index 4 we have to calculate the maximum sum that can be achieved if we go backwards from 4 to 1. So there is a repeated calculation. If we had somehow stored the result of maximum sum that can be achieved if we go backwards from index 4 to index 1 beforehand we could have saved the repeated calculation. Hence we need to first precompute that for every index ‘i’ what is the maximum sum achievable if we go backwards from index ‘i’ to 1 to save time. How do we do this?
We have to do this in the best way possible..Going by the constraints we have to come up with an 0(N) solution.
Now this is achievable. Let’s see how. If I am at index ‘i’ I have two choices, to go 1 step back or go 2 steps back. So the optimal choice at ‘i’ will be to either take a[i-1] and then add the maximum sum achievable from index i-1 to 1. Or take a[i-2] and then add the maximum sum achievable from index i-2 to 1. I will take the maximum of these two. Please note I will note add the current value i.e a[i] to backward[i] because if I got from index ‘i’ to index ‘j’ only score of index ‘j’ will be added to the total score. So maximum sum achievable from index ‘i’ to 1 can be calculated as,
backward[i] = max(a[i-1]+backward[i-1], a[i-2]+backward[i-2]) Please note that backward[i-1] and backward[i-2] will be computed beforehand when I will be calculating backward[i] and therefore I save repeated calculation by memoizing it. Again this backward[i] will be needed when I will be calculating for backward[i+1] and backward[i+2] states.
Now consider the base cases. Suppose I am at the first Index. In that case I have already reached my destination. Hence backward[1] will always be equals to 0. Also if I am at index 2, I have only 1 option, ie to go to index 1 and finish. Hence backward[1] = a[1]. I am calculating for index 1 and 2 separately just to ensure that array index doesn’t go out of bounds. More realistically when I am index 1 I have no option. And when I am at index 2 I have only one option i.e 1 step backward instead of 2 options.
So to sum up , I will calculate backward array like this
backward[1] = 0; if(n>=2)
backward[2] = a[1]; for(i=3;i<=N;i++)
backward[i] = max(a[i-1]+backward[i-1],a[i-2]+backward[i-2]);
Ok so what’s next?
Coming back to our forward move, now we have to make an optimal move in O(n) starting from index ‘k’. Again we have two choices , go 1 step ahead or go 2 steps ahead. But we have to also keep in mind we have to go backwards as well at some point of time from some index and can’t just keep moving forward only. Hence if we somehow keep another array like backward array say endForwardAtIndex where endForwardAtIndex[i] will denote the maximum sum achievable from index ‘k’ to index ‘i’ and with backward[i] stored we can easily figure out what is the maximum sum achievable if I finish my forward move at index ‘i’ starting from index ‘k’ and then move backwards all the way till 1. This will be achieved by endForwardAtIndex[i] + backward[i].
So if we have this endForwardAtIndex and backward array ready, How can we find the answer ? Well it will be max (endForwardAtIndex[i] + backward[i]) where ‘i’ will range from k to n.
How?
Because think for a moment, I just said endForwardAtIndex[i] + backward[i] denotes that if I end my forward move at index ‘i’ and with the maximum sum achievable from index ‘i’ to 1 by going backwards ready, I can find out what is the maximum sum achievable if I end my forward move at index ‘i’ and then going back to index 1. In short I can figure out what is the maximum sum if I end my forward move at index ‘i’.
Since I start from index ‘k’ the minimum index where I can end my forward move is at index ‘k’ itself.(this will denote a case where I don’t take any forward move at all and only go backwards). Similarly the maximum index I can end my forward move is at index ’n’ i.e last index. Hence maximum of all endForwardAtIndex[i] + backward[i] will give us the required answer where I = k to n. Because only within these indices I can end my forward move and once I have ended at index ‘i’ I have in store the maximum sum that can be achieved from index ‘i’ all the way to 1 in backward[i], therefore I can figure out that if I end my forward move at index ‘i’ what is the maximum sum achieved.
So if we can somehow calculate the endForwardAtIndex in O(n) we are done .
So what are the base cases?
Say we want to end our forward move at index K. (i.e we are not moving forward at all and only moving backward) the maximum sum achieved going in forward direction is 0. Hence total sum achieved = 0 + backward[k] .
Again if we want to end our forward move at index K+1 , the maximum sum achieved from index K to index K+1 can only be a[k+1]
Now for index k+2 onwards,
endForwardAtIndex[i] = a[i] + max(endForwardAtIndex[i-1],endForwardAtIndex[i-2])
Why? Because if we are ending at index ‘i’, we must consider the element at index ‘i’ and have two choices actually. I can either come to index ‘i’ from index i-1 or from index ‘i-2’. So which one I will add to a[i]? Obviously the maximum sum from these 2 ,isn’t it?. I will only add the maximum sum of these 2 paths to a[i].
In this way we can calculate endForwardAtIndex array.
There is one small thing to keep in mind: endForwardAtIndex[i] considers the current element whereas backward[i] doesn’t considers the current element. If you go and check the code of my backward[i] I am not adding a[i] to backward[i] but in endForwardAtIndex[i] I am adding a[i] to it. Why this is so?
Consider this array 2 4 5 7 1 and lets say I am checking the maximum sum achieved if I end my forward move at index 4 starting from index 2. endForwardAtIndex[4] = 5+7 = 12.Then I will add it with backward[4]. Now had I considered a[i] or current element in backward[i] , backward[4] would have yielded 18. And hence endForwardIndex[4] + backward[4] would have yielded 12 + 18 or rather 5 + 7 + 7 + 5 + 4 + 2. Check that 7 is being added 2 times but that should not be the case. Once I have reached index 4 and added 7 to my sum , I cant include 7 anymore if I am starting a backward move from it. Because if I go from index ‘i’ to index ‘j’ only the value of index ‘j’ gets added.
Therefore I wont consider a[i] in backward[i] as I have already considered the last element in endForwardAt[i].
Algorithm
n = size of the array a = array
// computing the backward array first
backward[1] = 0; if(n>=2)
backward[2] = a[1]; for(i=3;i<=n;i++)
backward[i] = max(a[i-1]+backward[i-1],a[i-2]+backward[i-2]);
//computing the endForwardAtIndex array endForwardAtIndex[k] = 0; if(k+1<=n)
endForwardAtIndex[k+1] = a[k+1]; for(ll i=k+2;i<=n;i++)
endForwardAtIndex[i] = a[i] + max(endForwardAtIndex[i-1],endForwardAtIndex[i-2]);
// computing the maximum with the help of 2 arrays
maximum =-INF; // lowest possible value for(i=k;i<=n;i++)
maximum = max(maximum , endForwardAtIndex[i] +backward[i]);
print(maximum)
Since we calculated values based on pre computed values and saved repeated calculation, algorithm paradigm used here is Dynamic Programming. But I didn’t mention the word DP throughout this blog because I wanted to keep it simple and realistic. Often people get intimidated by this terms Dp, Graphs and all. So its a try to make them realise these things are very realistic and actually not that tough as we think it is.
If you like my post , do not hesitate to give a clap. It MATTERS and serves as a motivation to write more posts like these.
Also checkout my YouTube Channel.
