Bakslat Bakslat - 2 months ago 6
C++ Question

Algorithm to find the best profit in a vector in c++

If i have a for an example vector: vector prices {18, 8, 10, 16, 14}; Which is in another class. I have the class Trade:

class Trade {

protected:
int buyTime;
int sellTime;

public:
Trade(const int buyTimeIn, const int sellTimeIn)
: buyTime(buyTimeIn), sellTime(sellTimeIn) {
}


What is the best way to make a function which get a random vector within the trade class and returns a Trade object. The function needs to find the best "profit" in the vector if you buy for an example at day 1 which is 8 and sell on day 3 which is 16. Also the sell cannot be before the buy. Each input in the vector represents the price in each day.

for (int s = 0; s <= prices.size(); ++s) {
for (unsigned int i = 0; i <= vectorTotal; ++i) {
allData.push_back(prices.at[s] - prices.at[vectorTotal - i]);
}
}

void printVector(const vector<int>& allData){
cout << "Vector: ";

for (unasigned int i = 0; i < allData.size(); i++) {
cout << allData[i] << " ";
}
}
}


This is my try to check the every number with its next ones but I cannot seem to figure out how to print them or even if i am on the right track.

Answer

Given a vector of prices, if the sell has to come after the buy (no short-selling is allowed), then there's an O(n) algorithm that goes like this:

  double Best_profit(const vector<double>& price){
    int n=price.size(),i; double max_price=-1e+308,profit,max_profit=0;
    for(i=n-1;i>=0;i--){
      if(price[i]>max_price) max_price=price[i];
      profit=max_price-price[i];
      if(profit>max_profit) max_profit=profit;
    }
    return max_profit;
  }

The variable max_price finds the highest price after the current day i. The variable profit calculates the profit one would get if a commodity is bought on the current day and sold at that max_price (which has to come after Day i), and finally the max_profit finds the best profit one can make. It is crucial to work backwards. This algorithm has to do with dynamic programming.