**一. 題目描述** Say you have an array for which the i-th 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. **二. 題目分析** 題目的意思是輸入一個表示一支股票每天股價的數組，第`i`個元素代表第`i`天的股價，只允許買入賣出一次，問怎么買賣使得收益最大？ 首先想到的是把原始估價序列變成差分序列，則可轉化為求數組的最大子段和。 或者，可以用類似動態規劃的思想，假設在第`i`天買入，什么時候能賺到的最多的錢呢？不外乎就是在第`i + 1`?到?`n`天中選擇最大的股價減去第`i`天的股價。 **三. 示例代碼** ~~~ // 第二種方法 #include <iostream> #include <vector> using namespace std; class Solution { public: int maxProfit(vector<int> &prices) { if (prices.size() == 0) return 0; int maxPrice = prices[prices.size() - 1]; int profit = 0; for(size_t i = prices.size() - 1; i >= 0; i--) { maxPrice = max(maxPrice, prices[i]); profit = max(profit, maxPrice - prices[i]); } return profit; } }; ~~~ **四. 小結** 與該題相關的題目還有好幾道。后續更新…