LeetCode #123

Description:

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).

Example:

``````Note
``````

Time: O(n)

Code:

``````class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<2) return 0;

int len = prices.size();
vector<int> sell_profit(len, 0);
vector<int> buy_profit(len, 0);

int min_price=prices[0];
for(int i=1; i<prices.size(); ++i){
sell_profit[i] = max(sell_profit[i-1], prices[i]-min_price);
if(prices[i]<min_price)
min_price=prices[i];
}

int max_price=prices[len-1];
for(int i=len-2; i>=0; --i){
buy_profit[i] = max(buy_profit[i+1], max_price-prices[i]);
if(prices[i]>max_price)
max_price=prices[i];
}

int max_profit = 0;
for(int i=0; i<len; i++){
max_profit = max(max_profit, sell_profit[i]+buy_profit[i]);
}

return max_profit;
}
};
``````

Solution 2, 这个是调用一个general的函数来计算每一天的max profit，不是很好写。

``````class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<2) return 0;

int len = prices.size();
vector<int> sell_profit = profitSequence(prices, 1, len, true);
vector<int> buy_profit = profitSequence(prices, len-2, -1, false);

int max_profit = 0;
for(int i=0; i<len; i++){
max_profit = max(max_profit, sell_profit[i]+buy_profit[i]);
}

return max_profit;
}

vector<int> profitSequence(const vector<int>& prices, int start, int end, bool flag_ascend) {
vector<int> result(prices.size(), 0);

if(prices.empty()) return result;

int incr = flag_ascend? 1 : -1;
int ind_start = flag_ascend? 0 : prices.size()-1;
int cmp_price=prices[ind_start];
int max_profit=0;

for(int i=start; i!=end; i = i + incr){
if(flag_ascend){
if(prices[i]-cmp_price > max_profit){
max_profit = prices[i]-cmp_price;
}
if(prices[i]<cmp_price)
cmp_price=prices[i];
}
else{
if(cmp_price-prices[i] > max_profit){
max_profit = cmp_price-prices[i];
}
if(cmp_price<prices[i])
cmp_price=prices[i];
}
result[i] = max_profit;
}

return result;
}
};
``````