Best Time to Buy and Sell Stock - LeetCode
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 104
解析
直观的办法是把每天作为买入起点，在每一次内计算最大值，最终全盘比较。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(len(prices) - 1):
max_profit = 0
for j in range(i + 1, len(prices)):
if max_profit < prices[j] - prices[i]:
max_profit = prices[j] - prices[i]
if max_profit > profit:
profit = max_profit
return profit
结果是超时了，两个循环嵌套的必然结果。不做讨论了，想想其他办法。
下面的方法更好一些，从前往后循环，一个变量存储当前的最小值，并在此基础上计算Max profit。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = prices[0]
max_profit = 0
for i in range(len(prices)):
if prices[i] < min_price:
min_price = prices[i]
elif prices[i] - min_price > max_profit:
max_profit = prices[i] - min_price
return max_profit
class Solution {
public int maxProfit(int[] prices) {
int max_profit = 0;
int min_price = prices[0];
for (int price:prices) {
if (price < min_price){
min_price = price;
} else if (max_profit < price - min_price) {
max_profit = price - min_price;
}
}
return max_profit;
}
}
class Solution {
public:
int maxProfit(vector<int>& prices) {
int max_profit = 0;
int min_price = prices[0];
for (int price : prices){
if (price < min_price){
min_price = price;
}
else if (max_profit < price - min_price){
max_profit = price - min_price;
}
}
return max_profit;
}
};