一：LeetCode 121 Best Time to Buy and Sell Stock
題目：
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.
鏈接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
分析：此題就是選擇買入賣出股票的最大收益，對於第i天賣出的最大收益即為第i天的股市價格減去[0,i-1]天內的最小股市價格，當第i天的股市價格比漆面最低股市價格還低，則更新最低股市價格。然後取最大的股市收益，為DP問題。用profit[i]表示第i天的收益，則minBuyPrice = min(minBuyPrice, prices[i]),並且profit[i] = prices[i]-minBuyPrice. 然後取profit中的最大值。
class Solution {
public:
int maxProfit(vector &prices) {
int n = prices.size();
if(n == 0) return 0;
int maxPro = 0;
int minBuyPrice = prices[0];
for(int i = 1; i < n; i++){
minBuyPrice = min(minBuyPrice, prices[i]); // 用於記錄當前天買進的最小值 minBuyPrice[i+1] = min(minBuyPrice[i], nums[i])
if(maxPro < (prices[i]- minBuyPrice)){ // 全局最大利益是否小於當天的利益
maxPro = prices[i]- minBuyPrice;
}
}
return maxPro;
}
};
題目：
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
鏈接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
分析：此題是上題的變形，買入賣出的次數沒有限制，但是第二次買入必須在第一次賣出的時間節點之後，，此時存在一個局部最優，即 2 4 5 3 6 8,此時8-2一定小於5-2+8-3,,因此就有取數組每次遞增的收益即為局部最優，然後所有的局部最優加起來就是全局最優
class Solution {
public:
int maxProfit(vector &prices) {
int n = prices.size();
if(n == 0) return 0;
int minBuyPrice = prices[0];
int sumResult = 0;
/*for(int i = 0; i < n; i++){
if(i+1 < n && prices[i] >= prices[i+1]){ // 局部最優在於當prices[i] >= prices[i+1]
sumResult += prices[i]-minBuyPrice; //既可用prices[i]-minBuyPrices了找到局部最優了--全部加起來就是全局最優解了
minBuyPrice = prices[i+1];
}else{
if(i+1 == n) sumResult += prices[i]-minBuyPrice;
}
}*/
for(int i = 1; i < n; i++){
if(prices[i] < prices[i-1]){ // 在i處有一個局部最優,所有的局部最優和就是全局最優
sumResult += prices[i-1]- minBuyPrice;
minBuyPrice = prices[i];
}
}
sumResult += prices[n-1]- minBuyPrice;
return sumResult;
}
};
後來在discuss中看到一段更牛逼的代碼：只要十行：
class Solution {
public:
int maxProfit(vector &a) {
int profit = 0;
for (int i = 1; i < a.size(); ++i) {
if (a[i] > a[i-1]) {
profit += a[i]-a[i-1];
}
}
return profit;
}
};
三：LeetCode 123 Best Time to Buy and Sell Stock III
題目：
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
鏈接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
分析：此題亦即變形，也就是求交易次數最多為兩次。當然有兩種方法，第一種暴力，對於每個i，我們求[0,i]與[i,n-1]兩次收益，然後求和，遍歷i，可以取其中的最大值，需要O(N^2)的時間。第二種方法是動態規劃，用兩個數組，第一個數組f1[i]用來表示在[0,i]內進行買入賣出的最大收益，用f2[i]表示在[i,n-1]內進行買入賣出的最大收益。然後最大收益即為max(f1[i]+f2[i])，如何求f1[i]和f2[i]，，第一題的方法已經給出了。
class Solution {
public:
int maxProfit(vector &prices) {
int n = prices.size();
if(n <= 1) return 0;
vector f1(n); // 表示在[0,i]內進行買入賣出所能獲得的最大profit
vector f2(n); // 表示在[i, n-1]內進行買入賣出所能獲得的最大profit 結果就為max(f1[i]+f2[i])
int minPrice = prices[0];
for(int i = 1; i < n; i++){
minPrice = min(minPrice, prices[i]);
f1[i] = max(f1[i-1], prices[i]- minPrice);
}
int maxPrice = prices[n-1];
for(int i = n-2; i >=0; i--){ // 這裡要從後往前遍歷
maxPrice = max(maxPrice, prices[i]);
f2[i] = max(f2[i+1], maxPrice - prices[i]);
}
int maxResult = 0;
for(int i = 0; i < n; i++)
maxResult = max(maxResult, f1[i]+f2[i]);
return maxResult;
}
};
