Amazon Question: Best time buy sell stock

Problem: Given an array in which its i^th element is the price of the stock on day i, design an algorithm to maximize the profit than can be made by buying and selling the stock on these days.

Note that you can not engage in multiple transaction at the same time i.e. you must sell the stock before you buy again. 

Solution: Take the following steps:

1. Start from the start and go until prices[i + 1]  > prices[i].
2. i + 1 is the day for buying the stock.
3. Now again traverse the array and go until prices[i] < prices[i - 1].
4. i - 1 is the day for selling the stock.
5. Push these days to result.
6. Repeat the above steps until you reach the end of the given array of stock prices.

Implementation:

void stockBuySell(std::vector<int>& prices)

{

int len = prices.size();

if(len <= 1)

return;

int i = 0;

std::vector<StockBuySellPrices> result;

while(i < len - 1)

{

while((i < len - 1) && (prices[i+1] <= prices[i]))

++i;

if(i == len - 1)

break;

StockBuySellPrices price(prices[i++]);

while((i < len) && (prices[i] >= prices[i-1]))

++i;

if(price.buy < prices[i - 1])

{

price.sell = prices[i-1];

result.push_back(price);

}

}

len = result.size();

int totalProfit = 0;

for(int i = 0; i < len; ++i)

{

std::cout<<i<<": Buy at price: "<<result[i].buy<<" and Sell at price: "<<result[i].sell<<'\n';

totalProfit += (result[i].sell - result[i].buy);

}

std::cout<<"Total Profit: "<<totalProfit<<std::endl;

}

Complexity: O(n)