Problem
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 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5
(not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
題意
懷疑智商題之二：又是買股票和賣股票的問題预茄。題目給定一個數(shù)組prices,prices[i]代表第i天股票的價格侦厚。要求找出最大利潤。
限制條件是刨沦，在這n天中只能完成一次買入和賣出操作。（Best Time to Buy an Sell Stock II中召庞，可無限次買入和賣出）侧蘸。
分析
初始化minPrice = 0, maxPro = 0鹉梨。
從第0天開始，通過for循環(huán)遍歷數(shù)組晌坤，在訪問prices[i]時旦袋，做兩次比較：
- 第一次比較
prices[i]和當(dāng)前minPrice的值 - 第二次比較
prices[i] - minPrice和當(dāng)前maxPro
這道題中要說明其DP思想是一件讓人很為難的事情···簡單來說，這道題是從第一天開始疤孕，逐步擴(kuò)大問題規(guī)模，記錄出現(xiàn)過的最低價格鹉戚，每一天的價格都記錄一個利潤值，比較該利潤值與到目前為止的最大利潤值抹凳，更新最大利潤值，直到問題規(guī)模增長到n為止失都。
Code
//Runtime: 6ms
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) return 0;
int minPrice = prices[0];
int maxPro = 0;
for (int i = 0; i < prices.size(); i++){
minPrice = min(minPrice, prices[i]);
maxPro = max(maxPro, prices[i] - minPrice);
}
return maxPro;
}
};
