Bakslat - 1 year ago 67
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 sellTime;

public:
}
``````

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.

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download