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].
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if (A.length == 0) {
return 0;
}
int maxValue = A[A.length-1];
int minValue = A[A.length-1];
for (int i=A.length-2; i>=0; i--) {
if (maxValue < A[i] && i > 0) {
maxValue = A[i];
}
if (minValue > A[i]) {
minValue = A[i];
}
}
int rtn = maxValue-minValue;
if (rtn < 0) {
rtn = 0;
}
return rtn;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if (A.length == 0) {
return 0;
}
int maxValue = A[A.length-1];
int minValue = A[A.length-1];
for (int i=A.length-2; i>=0; i--) {
if (maxValue < A[i] && i > 0) {
maxValue = A[i];
}
if (minValue > A[i]) {
minValue = A[i];
}
}
int rtn = maxValue-minValue;
if (rtn < 0) {
rtn = 0;
}
return rtn;
}
}
[23171, 21011, 21123, 21366, 21013, 21367]
[80, 10, 20, 30, 50, 20]
[10, 20, 30, 50, 20]
[]
function result: 356
function result: 40
function result: 40
function result: 0
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if (A.length == 0) {
return 0;
}
int maxValue = A[A.length-1];
int minValue = A[A.length-1];
for (int i=A.length-2; i>=0; i--) {
if (maxValue < A[i] && i > 0) {
maxValue = A[i];
}
if (minValue > A[i]) {
minValue = A[i];
}
}
int rtn = maxValue-minValue;
if (rtn < 0) {
rtn = 0;
}
return rtn;
}
}
[23171, 21011, 21123, 21366, 21013, 21367]
[80, 10, 20, 30, 50, 20]
[10, 20, 30, 50, 20]
[]
function result: 356
function result: 40
function result: 40
function result: 0
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if (A.length == 0) {
return 0;
}
int maxValue = A[A.length-1];
int minValue = A[A.length-1];
for (int i=A.length-2; i>=0; i--) {
if (maxValue < A[i] && i > 0) {
maxValue = A[i];
}
if (minValue > A[i]) {
minValue = A[i];
}
}
int rtn = maxValue-minValue;
if (rtn < 0) {
rtn = 0;
}
return rtn;
}
}
The following issues have been detected: wrong answers.
For example, for the input [5, 4, 3, 2, 1] the solution returned a wrong answer (got 3 expected 0).
max profit is after global maximum and before global minimum
got 8 expected 3
large value (99) followed by short V-pattern (values from [1..5]) repeated 100 times
chaotic sequence of 200K values from [100K..120K], then 200K values from [0..100K]
got 120000 expected 100000