一. 題目描述
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
#include
using namespace std;
class Solution {
public:
int maxProfit(vector &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;
}
};
四. 小結
與該題相關的題目還有好幾道。後續更新…
