Codility's MaxProfit – Luís Ramalho
Our goal is to basically compute the maximum profit that ends in a given position. Thus, if we assume that the maximum profit that ends in a position i equals maxProfit then the maximum slice ending in position i + 1 is going to be max(0, maxProfit + (ai - ai - 1)).
http://rafal.io/posts/codility-max-profit.html
http://www.martinkysel.com/codility-maxprofit-solution/
Read full article from Codility's MaxProfit – Luís Ramalho
A zero-indexed array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q].
For example, consider the following array A consisting of six elements such that:
A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367
If a share was bought on day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.
Write a function,
int solution(int A[], int N);
that, given a zero-indexed array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.
For example, given array A consisting of six elements such that:
A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367
the function should return 356, as explained above.
MaxProfit is a problem where one must compute the maximum possible earnings given a log of stock prices. Note that before attempting this problem, you should read the material on maximum slice.Our goal is to basically compute the maximum profit that ends in a given position. Thus, if we assume that the maximum profit that ends in a position i equals maxProfit then the maximum slice ending in position i + 1 is going to be max(0, maxProfit + (ai - ai - 1)).
int maxProfit = 0;
int maxSlice = 0;
for (int i = 1; i < a.length; i++) {
maxProfit = Math.max(0, maxProfit + (a[i] - a[i - 1]));
maxSlice = Math.max(maxSlice, maxProfit);
}
if (maxSlice < 0) {
maxSlice = 0;
}
return maxSlice;http://rafal.io/posts/codility-max-profit.html
http://www.martinkysel.com/codility-maxprofit-solution/
This problem is extremely similar to the maximum subarray problem which is solved in time O(n) using Kadane’s algorithm.
For the maximum profit, the gist is that we want to buy as low as possible, and sell as high as possible. Kadane’s algorithm part will keep track of the highest possible profit so far, and another variable will keep track of the minimal buy cost we’ve encountered so far, so this is always the one we should prefer.
public int maxProfit(int[] A) {
if(A.length == 1 || A.length == 0){
return 0;
}
int maxSoFar = 0;
int maxEndingHere = 0;
int minPrice = A[0];
for(int i = 1; i < A.length; i++){
maxEndingHere = Math.max(0, A[i] - minPrice);
minPrice = Math.min(minPrice, A[i]);
maxSoFar = Math.max(maxEndingHere, maxSoFar);
}
return maxSoFar;
}
travel from the last element to the first one.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
def solution(A):
days = len(A)
# If the number of days is zero or one, there
# is no time to get profit.
if days < 2:
return 0
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)
return max_profit
|
Read full article from Codility's MaxProfit – Luís Ramalho
