Created
March 25, 2020 16:56
-
-
Save victorkurauchi/e21fff36ef830be015dd6997f63ce2c7 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// you can write to stdout for debugging purposes, e.g. | |
// console.log('this is a debug message'); | |
function solution(A) { | |
// write your code in JavaScript (Node.js 8.9.4) | |
let maxSoFar = 0; | |
let maxEndingHere = 0; | |
let minPrice = A[0]; | |
for (let i = 0; i < A.length; i++) { | |
// console.log(A[i]) | |
// console.log('min price', minPrice); | |
maxEndingHere = Math.max(0, A[i] - minPrice); | |
// console.log('max ending here', maxEndingHere) | |
minPrice = Math.min(minPrice, A[i]); | |
maxSoFar = Math.max(maxEndingHere, maxSoFar); | |
} | |
if (maxSoFar <= 0) return 0; | |
return maxSoFar; | |
} | |
/* | |
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, | |
function solution(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]. | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment