lundi 28 septembre 2020

What is the time complexity of the following code fragment for Stock Buy & Sell?

Recently I was trying the problem of Stock Buy and Sell in which we can buy a stock on any day and sell it on any upcoming day, and we have to find the maximum profit that we can get.

The solution that first came to my mind was the code below but I'm not able to determine its time complexity. It would be very helpful if you can help with this.

int maxProfit(int price[], int start, int end){
  if(end<=start)
    return 0;

  int profit=0;

  for(int i=start; i<end; i++){

    for(int j=i+1; j<=end; j++){

      if(price[j]>price[i]){

        int curr_profit=price[j]-price[i]+maxProfit(price,start,i-1)+maxProfit(price,j+1,end);
        profit=max(profit,curr_profit);
      }
    }

    return profit;
  }
}

Aucun commentaire:

Enregistrer un commentaire