# Best Time To Buy And Sell Stock

Given an array of prices, one must find when they would buy and sell stocks so that they would get the maximum profit. A stock should be bought before being able to sell it (Question 1, Question 2, Question 3)

- Let's consider a brute force approach where we would use two loops to find the difference between the bought and sold stock for each of the given prices
- This approach would take O(n²) time complexity and would not be ideal for large inputs

`public int maxProfit(int[] prices) {`

int diff=0;

int max_profit=0;

for(int i=0;i<prices.length;i++){

for(int j=i+1;j<prices.length;j++){

diff=prices[j]-prices[i];

max_profit=Math.max(diff,max_profit);

}

}

return max_profit;

}

- The approach is to find a minimum stock price and find a stock after that which is greater than this stock to gain a profit.
- Let us take a temporary variable to store the minimum values and calculate the profit gained as we traverse through the array
- The time complexity of the algorithm is O(n)

`public int maxProfit(int[] prices) {`

int least_stock=Integer.MAX_VALUE;

int max_profit_total=0;

int max_profit_now=0;

for(int i=0;i<prices.length;i++){

if(prices[i]<least_stock)

least_stock=prices[i];

max_profit_now=prices[i]-least_stock;

max_profit_total=Math.max(max_profit_now, max_profit_total);

}

return max_profit_total;

}

- Another variant of stock questions to buy a stock infinite number of times can be solved by finding a buying day with least stock price and finding a seliing day with maximum stock price
- buy the stocks whenever there is a least stock in a increasing section and sell the stock in the peak of the increasing section

`public int maxProfit(int[] prices) {`

int buy_day=0;

int sell_day=0;

int max_profit=0;

for(int i=1; i<prices.length; i++){

if(prices[i]>prices[i-1])

sell_day++;

else{

max_profit+=prices[sell_day]-prices[buy_day];

buy_day=sell_day=i;

}

}

max_profit+=prices[sell_day]-prices[buy_day];

return max_profit;

}

- This has a time compelxity of O(n) and O(1) space complexity
- To sell the stocks atmost twice we can keep 2 arrays one to traverse ahead and one to traverse backward
- we find the stock profit while we travel forward and we find the stock profit while we travel backward and store the values in temporory arrays
- this way we get the the stock profits when sold twice as the sum of values in these two temporary values

`public int maxProfit(int[] prices) {`

int n=prices.length;

int max_backward_profit=Integer.MIN_VALUE;

int max_forward_profit=Integer.MIN_VALUE;

int total_profit=0;

int least_value=prices[0];

int max_value=prices[n-1];

int[] forward_array=new int[n];

int[] backward_array=new int[n];

for(int i=0;i<n;i++){

if(prices[i]<least_value)

least_value=prices[i];

else if(max_forward_profit<prices[i]-least_value)

max_forward_profit=prices[i]-least_value;

forward_array[i]=max_forward_profit;

}

for(int i=n-1;i>=0;i--){

if(prices[i]>max_value)

max_value=prices[i];

else if(max_backward_profit<max_value-prices[i])

max_backward_profit=max_value-prices[i];

backward_array[i]=max_backward_profit;

}

for(int i=0;i<n;i++){

if(total_profit<forward_array[i]+backward_array[i]){

int sum=forward_array[i]+backward_array[i];

total_profit=Math.max(total_profit,sum);

}

}

return total_profit;

}

- This takes O(n) time complexity and O(n) extra space