Tasks Details
easy
1.
MaxProfit
Given a log of stock prices compute the maximum possible earning.
Task Score
100%
Correctness
100%
Performance
100%
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] = 21367If 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,
class Solution { public int solution(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] = 21367the 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].
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 8
Time spent on task 18 minutes
Notes
not defined yet
Task timeline
Code: 05:52:35 UTC,
java,
autosave
Code: 06:05:40 UTC,
java,
autosave
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[0];
int min = A[1];
int benefit = A[1] - A[0];
for (int value : A) {
if (value < A[1]) {
min = value;
} else {
benefit = Math.max(benefit, value - min);
}
}
return benefit;
}
}
Code: 06:05:41 UTC,
java,
verify,
result: Failed
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[0];
int min = A[1];
int benefit = A[1] - A[0];
for (int value : A) {
if (value < A[1]) {
min = value;
} else {
benefit = Math.max(benefit, value - min);
}
}
return benefit;
}
}
Analysis
expand all
Example tests
1.
0.008 s
WRONG ANSWER,
got 2160 expected 356
Code: 06:06:26 UTC,
java,
autosave
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int min = A[0];
int max = A[1];
int benefit = A[0] - A[1];
for (int value : A) {
if (value < A[1]) {
min = value;
} else {
benefit = Math.max(benefit, value - min);
}
}
return benefit;
}
}
Code: 06:06:26 UTC,
java,
verify,
result: Failed
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int min = A[0];
int max = A[1];
int benefit = A[0] - A[1];
for (int value : A) {
if (value < A[1]) {
min = value;
} else {
benefit = Math.max(benefit, value - min);
}
}
return benefit;
}
}
Analysis
expand all
Example tests
1.
0.008 s
WRONG ANSWER,
got 2160 expected 356
Code: 06:06:46 UTC,
java,
verify,
result: Failed
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int min = A[0];
int max = A[1];
int benefit = A[1] - A[0];
for (int value : A) {
if (value < A[1]) {
min = value;
} else {
benefit = Math.max(benefit, value - min);
}
}
return benefit;
}
}
Analysis
expand all
Example tests
1.
0.008 s
WRONG ANSWER,
got 0 expected 356
Code: 06:07:20 UTC,
java,
verify,
result: Failed
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[0];
int min = A[1];
int benefit = A[1] - A[0];
for (int i = 0; i < A.length; i++) {
if(A[i] < A[1]) {
min = A[i];
} else {
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Analysis
expand all
Example tests
1.
0.004 s
WRONG ANSWER,
got 2160 expected 356
Code: 06:08:18 UTC,
java,
verify,
result: Failed
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[0];
int min = A[1];
int benefit = A[1] - A[0];
System.out.println(benefit);
for (int i = 0; i < A.length; i++) {
if(A[i] < A[1]) {
min = A[i];
} else {
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Analysis
expand all
Example tests
1.
0.004 s
WRONG ANSWER,
got 2160 expected 356
stdout:
-2160
Code: 06:08:31 UTC,
java,
autosave
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[1];
int min = A[0];
int benefit = A[1] - A[0];
System.out.println(benefit);
for (int i = 0; i < A.length; i++) {
if(A[i] < A[1]) {
min = A[i];
} else {
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Code: 06:08:32 UTC,
java,
verify,
result: Failed
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[1];
int min = A[0];
int benefit = A[1] - A[0];
System.out.println(benefit);
for (int i = 0; i < A.length; i++) {
if(A[i] < A[1]) {
min = A[i];
} else {
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Analysis
expand all
Example tests
1.
0.004 s
WRONG ANSWER,
got 0 expected 356
stdout:
-2160
Code: 06:09:04 UTC,
java,
autosave
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[1];
int min = A[0];
int benefit = A[1] - A[0];
for (int i = 0; i < A.length; i++) {
if(A[i] < A[1]) {
min = A[i];
} else {
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Code: 06:09:18 UTC,
java,
verify,
result: Failed
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[1];
int min = A[0];
int benefit = A[1] - A[0];
for (int i = 0; i < A.length; i++) {
if(A[i] < A[1]) {
min = A[i];
} else {
System.out.println("is : " + A[i] - min);
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Analysis
Compile error
Solution.java:15: error: bad operand types for binary operator '-'
System.out.println("is : " + A[i] - min);
^
first type: String
second type: int
1 error
Code: 06:09:26 UTC,
java,
verify,
result: Failed
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[1];
int min = A[0];
int benefit = A[1] - A[0];
for (int i = 0; i < A.length; i++) {
if(A[i] < A[1]) {
min = A[i];
} else {
System.out.println("is : " + (A[i] - min));
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Analysis
expand all
Example tests
1.
0.008 s
WRONG ANSWER,
got 0 expected 356
stdout:
is : 0 is : -2160 is : -2048 is : -1805 is : -2158 is : -1804
Code: 06:09:41 UTC,
java,
autosave
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[1];
int min = A[0];
int benefit = A[1] - A[0];
for (int i = 0; i < A.length; i++) {
if(A[i] < m) {
min = A[i];
} else {
System.out.println("is : " + (A[i] - min));
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Code: 06:09:43 UTC,
java,
verify,
result: Passed
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[1];
int min = A[0];
int benefit = A[1] - A[0];
for (int i = 0; i < A.length; i++) {
if(A[i] < min) {
min = A[i];
} else {
System.out.println("is : " + (A[i] - min));
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Analysis
expand all
Example tests
1.
0.004 s
OK
stdout:
is : 0 is : 112 is : 355 is : 2 is : 356
Code: 06:09:52 UTC,
java,
autosave
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[1];
int min = A[0];
int benefit = A[1] - A[0];
for (int i = 0; i < A.length; i++) {
if(A[i] < min) {
min = A[i];
} else {
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Code: 06:09:53 UTC,
java,
verify,
result: Passed
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[1];
int min = A[0];
int benefit = A[1] - A[0];
for (int i = 0; i < A.length; i++) {
if(A[i] < min) {
min = A[i];
} else {
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Analysis
Code: 06:09:57 UTC,
java,
final,
score:
100
class Solution {
public int solution(int[] A) {
if(A.length < 2) {
return 0;
}
int max = A[1];
int min = A[0];
int benefit = A[1] - A[0];
for (int i = 0; i < A.length; i++) {
if(A[i] < min) {
min = A[i];
} else {
benefit = Math.max(benefit, A[i] - min);
}
}
return benefit;
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
1.
0.008 s
OK
max_profit_after_max_and_before_min
max profit is after global maximum and before global minimum
max profit is after global maximum and before global minimum
✔
OK
1.
0.008 s
OK
expand all
Performance tests
medium_1
large value (99) followed by short V-pattern (values from [1..5]) repeated 100 times
large value (99) followed by short V-pattern (values from [1..5]) repeated 100 times
✔
OK
1.
0.008 s
OK
1.
0.156 s
OK
1.
1.036 s
OK
1.
0.516 s
OK