Best Time to Buy and Sell Stock
最后更新于：2022-04-01 22:57:15
**一. 题目描述**
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;
}
};
~~~
**四. 小结**
与该题相关的题目还有好几道。后续更新…
';