Arron Maximum Profit
Solutions This problem is an application of Find the Maximum Difference.
Basically, we need to find out the maximum difference between two numbers in the given array \(max(prices[j] - prices[i])\) with \(i<j\).
The bruce force approach is quadratic and does not pass all test cases: for each element we linearly find the biggest next value.
As discussed in Find the Maximum Difference, the general solution schema is the following:
1 2 3 4 5 6 7 8 9 auto currMin = INT_MAX; auto currMax = 0; for (auto i : prices) { currMin = min(currMin, i); currMax = max(i - currMin, currMax); } cout << currMax; As long as we iterate the array, currMin keeps track of the smallest element along the way.
[Read More]