Question Name: MaxProfit
For this question, we have to travel from the last element to the first one.
Solution to Max-Profit by codility
days = len(A)
# If the number of days is zero or one, there
# is no time to get profit.
if days < 2:
max_price_from_here = A[days-1]
max_profit = 0
for index in xrange(days-2, -1, -1):
# max_price_from_here-A[index] means the maximum
# profit from current day to end.
max_profit = max(max_profit, max_price_from_here-A[index])
max_price_from_here = max(A[index], max_price_from_here)
Hi Sheng, Thank you so much for sharing your solution! Can you please help me… I am trying to find the start and end index of the maximum-sum-subarray in your solution above. Can you please guide me?
You need to add two variables (for begin and end index) and re-write the code in line 14 and 15. If you really understand the solution, it is a easy job.
Here is my solution. Python 100/100.
From another direction. Thanks for sharing!
C solution, I got 100%
My solution in JAVA
Wow! Thanks for sharing another solution!
Not a good guess for the initialization value of min_price.
Thanks for your website !
Can you explain ? This is the value stated in the exercise.
For i == 1, min_price = min(A[i-1], min_price) may get incorrect value if A[i-1] is larger than 200000. Or in another example, when all values in A is larger than 200000, your function will return a wrong answer.
IMO, it is safer to initialize min_price with A.
Thanks again Sheng,
As stated each element of array A is an integer within the range [0..200,000] so there wouldn’t be such a case.
Sorry! I did not notice it. You are absolutely right 🙂
I have solved the problem with the following:
However I must admit that this does not work IF the cheapest price is in “the last day”.
I cannot agree with you. It’s apparently wrong. Maybe the code is incomplete and you should read the guildlines before posting the code 🙂
100%, 100% Java solution
Thanks for your contribution!
JS 100% with another point of view
Yet another variation:
thanks for maintaining this blog!
Here is my solution in Python:
I can’t see how is this max slice problem – only the first and the last element in the “slice” matter! So, I’m iterating from beginning til the end and pretending that I’m selling on that day. Of course, the best time to buy is the minimum price until that day.
C# with some functional fun
Python 100/100; Just find profit/loss first and then apply max slice algorithm. Much easier to understand the code, in my opinion.
I would like to thank Sheng for his contribution. I admire your unique approach to solving codility tests. Here is my C# solution where I basically keep track of smallest value and calculate profit using it