Best Time To Buy And Sell Stock

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Chaitra Rai

Chaitra Rai

1 Follower

Intimidated developer trying to find her way into technology dominant world