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,
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] = 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].
https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/
Here is a solution where I found on youtube
function solution(arr) {
let max = 0;
let acc = 0;
for(let i=1; i<arr.length; ++i) {
const diff = arr[i] - arr[i-1];
acc = acc + diff;
if(acc > 0) {
if(acc > max) {
max = acc;
}
} else {
acc = 0;
}
}
return max;
}
my question is below:
In this test case above, we know that array[five] - array[one] = 356 (we buy at day 5 and sell at day 1 to get max profit), in one transaction. We do not consider anything in between and that is what the question is asking
Using the accumulated difference sum and add them up together (hence other numbers come in and interference the calculation)
Why accumulated difference sum is equivalent to array[five] - array[one] = 356?
Consider the case of just three elements. It is clear that arr[i + 2] - arr[i + 1] + arr[i + 1] - arr[i] = arr[i + 2] - arr[i]
as the term arr[i + 1]
cancels out.
More generally, the sum arr[i + 1] - arr[i]
as i ranges from start
to end - 1
is a telescoping sum that equals arr[end] - arr[start]
. You can rigorously prove this by summation properties or induction.
Based on this, after converting the array of prices to a difference array, the answer is the maximum subarray sum, which can be found with Kadane's Algorithm.