Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock is an easy Sliding Window problem from the Blind 75. The key pattern is running minimum, and a good solution runs in O(n) time.
Problem
Using one buy before one sell, return the maximum non-negative profit from the price series.
Examples
Example 1
Input
[9,2,6,1,7,4]Output
6Example 2
Input
[8,3,6,2,9,5]Output
7Example 3
Input
[1]Output
0Approach
Track the lowest price seen so far; each day's best sale is today's price minus that minimum. Keep the largest such profit.
| Pattern | Running minimum |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
A falling price series has profit 0, not a negative number.