Best Time Buy Sell Stock III leetcode solution

Best Time Buy Sell Stock III leetcode solution

Best Time Buy Sell Stock III leetcode solution

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

Best Time Buy Sell Stock III leetcode solution

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

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;
}

Resolving technical problems:

Solve your technical problems instantly

We provide Remote Technical Support from Monday to Sunday, 7:00PM to 1:00 AM

Mail your problem details at writeulearn@gmail.com along with your mobile numberand we will give you a call for further details. We usually attend your problems within 60 minutes and solve it in maximum 2 days.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.