Question

/** * FUNCTION SIGNATURE: * PURPOSE: * PARAMETER: * RETURN VALUE: * Write the following function taking in an integer vector (vector &prices) consisting of all prices, in chronological order, for an hypothetical instrument. Your function recommends the maximum profit an investor can make by placing AT MOST one buy and one sell order in the time slice represented by your input vector. Remember BUY LOW, SELL HIGH

Answer 1

#include

using namespace std;

int maxProfit(int price[], int start, int end)

{

    // If the stocks can't be bought

    if (end <= start)

        return 0;

    // Initialise the profit

    int profit = 0;

    // The day at which the stock

    // must be bought

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

        // The day at which the

        // stock must be sold

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

            // If byuing the stock at ith day and

            // selling it at jth day is profitable

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

                // Update the current profit

                int curr_profit = price[j] - price[i]

                                  + maxProfit(price, start, i - 1)

                                  + maxProfit(price, j + 1, end);

                // Update the maximum profit so far

                profit = max(profit, curr_profit);

            }

        }

    }

    return profit;

}

// Driver code

int main()

{

    int price[] = { 100, 180, 260, 310,

                    40, 535, 695 };

    int n = sizeof(price) / sizeof(price[0]);

    cout << maxProfit(price, 0, n - 1);

    return 0;

}