Why This Works:
- Selling Price Perspective: By starting from the end, we focus on potential selling prices first and find the corresponding best buying prices as we move towards the beginning of the array.
- Efficient Tracking: The continual updates to
curMax
andmaxProfit
enable us to track the best selling price and corresponding profit efficiently in a single pass.
Summary:
By illustrating the steps through iterations, we can see how this reverse-traversal algorithm systematically calculates the best profit by considering each day as a potential selling day and finding the best corresponding buying day. This approach is efficient and aligns with the constraints of the problem, making it a powerful solution. It also showcases how a simple shift in perspective can lead to an elegant solution.
The key is that our curMax
may or may not be the max
that gets us the maximum profit. We still need to compare future curProfit
s that we calculate with our max profit thus far.