Stock Buy Sell to Maximize Profit

Given a stock n-day price, you can only trade at most once a day, you can choose to buy a stock or sell a stock or give up the trade today, the task is to find the maximum profit can reach.

Examples:

Input : arr = [1,2,10,9]
Output : 16
Explanation : 
You can buy in day 1,2 and sell in 3,4. profit :- 1 - 2 + 10 + 9 = 16 

Input : arr = [9,5,9,10,5]
Output : 5
Explanation : 
You can buy in day 2 and sell in 4. profit :- 5 + 10 = 5

Approach: Using Priority Queue
From the traversal of the stock price every day.
We consider the maximum return that can be obtained every day, and consider the greed to obtain the maximum return, then we can traverse from left to righ.
If the current price is greater than the lowest price encountered before, then make a transaction.

At the same time, the selling price is replaced by the buying price in the heap, that is, the current price is pushed into the queue (assuming that the current price is b, the element to be popped is a, and there is a c element, if a is still at that time, as the lowest Price, the difference is ca, and here has been taken by b to make the difference. So b must be pressed into the queue, because c-b+ba = ca), the lowest price before the pop-up, you can use the priority queue to make the previous Price orderly.

• Use the priority queue to store the current price encountered
• The daily new price is compared with the historical lowest price
• If it is higher than the lowest price, the lowest price will pop up and the answer will be updated at the same time, that is, the difference will be added
• Push in current price

Below is the implementation of above approach

#include <bits/stdc++.h>
using namespace std;
int getAns(vector<int> &a) 
{
    priority_queue<int, vector<int>, greater<int> > minheap;
    int res = 0;
    for (int k : a) 
    {
        // If k is higher than the lowest price encountered before
        if (minheap.size() > 0 && k > minheap.top()) 
        {
            // Yield is the current k-the lowest price encountered
            res += k - minheap.top();
            minheap.pop();
            minheap.push(k);   
        }
        // At the same time push the current value into the queue
        minheap.push(k);
    }
    return res;
}
int main() 
{
	vector<int> arr = { 1, 2, 10, 9 };
	cout<<getAns(arr);
}

Output :

16

Time Complexity: O(nlogn), n is the number of days, the complexity of the priority queue.
Space Complexity: O(n), n is the number of days.