121. Best Time to Buy and Sell Stock
Time = O(n), space=O(1)
Java:
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
int minPrice = Integer.MAX_VALUE;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
}
return maxProfit;
}
}
Python:
class Solution:
def maxProfit(self, prices: 'List[int]') -> 'int':
min_price = sys.maxsize
max_profit = 0
for i in range(0, len(prices)):
min_price = min(prices[i], min_price)
max_profit = max(max_profit, prices[i] - min_price)
return max_profit