• Tweet

• Tweet

Best Time Buy Sell Stock III leetcode solution

Best Time Buy Sell Stock III leetcode solution

You have an array for which the i^th 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).

Given problem involves a solution based on dynamic programming:

int maxProfit(vector<int> &prices) {
int mprof = 0;
if (prices.size()>1){
int maxprof = 0;
vector<int> mp; // max profit before each element
mp.push_back(0);
int st = *prices.begin();
for(int i = 1 ; i<prices.size();i++){ //compute mp vector
if (mprof < prices[i]-st){mprof = prices[i]-st;}
if (prices[i]<st){st = prices[i];}
mp.push_back(mprof);
}
mprof = 0;
int ed = *(prices.end()-1);
for (int i = prices.size()-2; i>=0; i–){
if (mprof < ed – prices[i] + mp[i]) { mprof = ed – prices[i] + mp[i];}
if (prices[i]>ed) {ed = prices[i];}
}
}
return mprof;
}

Best Time to Buy and Sell Stock II

Say you have an array for which the i^th 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).

If next element is greater , add difference to the result and continue this process for the entire array
int maxProfit(vector<int>& prices) {
int res=0;
if (prices.size()<2){return res;}
for (int i=1;i<prices.size();i++){
if (prices[i]>prices[i-1]){
res+=prices[i]-prices[i-1];
}
}
return res;
}