MaxProfit at app.codility.com/programmers in C++ Explained: Given a log of stock prices compute the maximum possible earning.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Lesson 9 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 30 Jul 2025
Problem
An 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(vector<int> &A);
that, given an 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.
Write an efficient algorithm for the following assumptions:
• N is an integer within the range [0..400,000];
• each element of array A is an integer within the range [0..200,000].
Note:
The N consecutive days have passed.For any profit, a number ahead in the array must subtract a number behind in the array, and the answer should be positive.
The maximum profit has been asked for. So comparison of slice sums (from the lesson) is not needed. So Kadane’s algorithm for maximum slice sum is not directly or wholly needed here.
No particular loss has been asked for. If 0 profit or no profit (all losses) was made, 0 is returned.
Strategy
Since one particular share price ahead must subtract one particular share price behind, then there should be a running maximum particular share price, which is assumed to be the greatest maximum share price. For maximum profit, the subtraction is between the greatest share price ahead and the least share price behind. As the given array is scanned from the beginning to the end, these values are looked for, while subtraction is being made to obtain the maximum profit.In the code below, scanning begins from i = 1 and not i = 0. A[i] is assumed to be the maximum particular running share price. A[0] is the first minimum share price on the left (assumed). As the given array is scanned, there is a minimum particular running share price, the first of which is A[0] (assumed). Still as the given array is scanned, subtraction is taking place between the running maximum price and the running minimum price, and comparison of the differences are obtained progressively. All those calculations take place in one body of the for-loop, leading to O(n) time.
Smart Solution
The solution() function is in the following program (read the code and comments). The running maximum share price is A[i].#include <iostream>The maximum running share price is implicit. The output is:
#include<vector>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
if (N<=1) return 0; // A[i] - A[i] = 0; needs at least two elements, for comparison
int maxDiff = 0;
int minValue = A[0];
for (int i=1; i < N; i++) {
if (A[i] < minValue)
minValue = A[i];
if ((A[i] - minValue) > maxDiff) //cannot be greater than 0 if indexes are the same
maxDiff = A[i] - minValue;
}
if (maxDiff <= 0) //losses were never calculated
return 0;
return maxDiff;
}
int main()
{
vector<int> B{23171, 21011, 21123, 21366, 21013, 21367};
int ret = solution(B);
cout << ret <<'\n';
vector<int> C{8, 9, 3, 6, 1, 2};
int ret1 = solution(C);
cout << ret1 <<'\n';
return 0;
}
356
3
The two if-statements in the for-loop body, are not really connected. They are independent. They do not form an if/else construct.
At app.codility.com/programmers the scoring and detected time complexity for this solution() is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Thanks for reading.