https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 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 Explanation: In this case, no transaction is done, i.e. max profit = 0.
中文翻譯:
給你每一天的股價。問你如果最多只能買賣一次
在所有可能性中，最大的獲利數字是多少?
[Solution]
Dynamic programming.
Answer of K is based on answer of K-1, and prices[K] - min prices of(0~K-1).
1.The relation between original problem and sub-problem.
At the end of K-th day(last day), there are only 2 mutually exclusive cases to get the profit.
Case 1: I sold the stock at K-th day.
You want to sell stock at K-th day, you must buy stock on i-th, which i<k.
You want to maximize the profit, so price[i] must be the minimum of prices[0]~prices[K-1].
Case 2: I did not sell the stock at K-th day.
Since you did not sell the stock on K-th day and it is the last day,
you must buy and sell the stock before K-th day.
And this is a sub-problem of original problem.
The max profit is max of case1 and case2.
2.The base case
When K=1, there is only one day and one price, your max profit can only be 0.
When K=2, you can buy on the first day and sell it on the second day.
But if you can't get profit from that, you should not buy/sell at all.
So the profit is max(prices[1]-prices[0], 0).
Let's write code~
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1) return 0;
vector<int> t(prices.size(),0);
t[0]=0;
t[1]=max(0,prices[1]-prices[0]);
int mini = min(prices[0],prices[1]);
for(int i=2;i<prices.size();i++){
t[i] = max(t[i-1], prices[i]-mini);
mini = min(prices[i],mini);
}
return t[prices.size()-1];
}
};
