# Best Time to Buy and Sell Stock ### Source - leetcode: [Best Time to Buy and Sell Stock | LeetCode OJ](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) - lintcode: [(149) Best Time to Buy and Sell Stock](http://www.lintcode.com/en/problem/best-time-to-buy-and-sell-stock/) ~~~ Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. Example Given an example [3,2,3,1,2], return 1 ~~~ ### 題解 最多只允許進行一次交易，顯然我們只需要把波谷和波峰分別找出來就好了。但是這樣的話問題又來了，有多個波峰和波谷時怎么辦？——找出差值最大的一對波谷和波峰。故需要引入一個索引用于記錄當前的波谷，結果即為當前索引值減去波谷的值。 ### Python ~~~ class Solution: """ @param prices: Given an integer array @return: Maximum profit """ def maxProfit(self, prices): if prices is None or len(prices) <= 1: return 0 profit = 0 cur_price_min = 2**31 - 1 for price in prices: profit = max(profit, price - cur_price_min) cur_price_min = min(cur_price_min, price) return profit ~~~ ### C++ ~~~ class Solution { public: /** * @param prices: Given an integer array * @return: Maximum profit */ int maxProfit(vector<int> &prices) { if (prices.size() <= 1) return 0; int profit = 0; int cur_price_min = INT_MAX; for (int i = 0; i < prices.size(); ++i) { profit = max(profit, prices[i] - cur_price_min); cur_price_min = min(cur_price_min, prices[i]); } return profit; } }; ~~~ ### Java ~~~ public class Solution { /** * @param prices: Given an integer array * @return: Maximum profit */ public int maxProfit(int[] prices) { if (prices == null || prices.length <= 1) return 0; int profit = 0; int curPriceMin = Integer.MAX_VALUE; for (int price : prices) { profit = Math.max(profit, price - curPriceMin); curPriceMin = Math.min(curPriceMin, price); } return profit; } } ~~~ ### 源碼分析 善用`max`和`min`函數，減少`if`的使用。 ### 復雜度分析 遍歷一次 prices 數組，時間復雜度為 O(n)O(n)O(n), 使用了幾個額外變量，空間復雜度為 O(1)O(1)O(1). ### Reference - soulmachine 的賣股票系列