<p>You are given an array <code>prices</code> where <code>prices[i]</code> is the price of a given stock on the <code>i<sup>th</sup></code> day, and an integer <code>fee</code> representing a transaction fee.</p>

<p>Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.</p>

<p><strong>Note:</strong></p>

<ul>
	<li>You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).</li>
	<li>The transaction fee is only charged once for each stock purchase and sale.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> prices = [1,3,2,8,4,9], fee = 2
<strong>Output:</strong> 8
<strong>Explanation:</strong> The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> prices = [1,3,7,5,10,3], fee = 3
<strong>Output:</strong> 6
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= prices.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= prices[i] &lt; 5 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= fee &lt; 5 * 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
    if(prices.size() <= 1)
        return 0;
    std::vector<int*> minmax;
    if(prices.front() > (*(prices.begin() + 1))) {
        minmax.emplace_back(&(*(prices.begin() + 1)));
    } else {
        minmax.emplace_back(&(*(prices.begin())));
    }

    for(int i = 1; i < prices.size(); i++) {
        if(minmax.size() % 2 == 0) {
            if(minmax.back() == &prices[i - 1] && prices[i] >= *minmax.back()) {
                minmax.back() = &prices[i];
            } else
                if(prices[i] < *minmax.back() && prices[i - 1] >= prices[i]) {
                    minmax.emplace_back(&prices[i]);
                }
        } else {
            if(minmax.back() == &prices[i - 1] && prices[i] <= *minmax.back()) {
                minmax.back() = &prices[i];
            } else
                if(prices[i] > *minmax.back() && prices[i - 1] <= prices[i]) {
                    minmax.emplace_back(&prices[i]);
                }
        }
    }
    if(minmax.size() % 2 != 0)
        minmax.pop_back();
    if(minmax.size() == 0)
        return 0;
    std::vector<std::pair<int*, int*>> intervals;// = {{minmax.front(), (*(minmax.begin() + 1))}};
    int last_start = 0;
    for(int i = 0; i < minmax.size(); i += 2) {
        // if(*minmax[i + 1] - *minmax[i] < fee)
        //     continue;
        if(intervals.size() == 0) {
            intervals.emplace_back(minmax[i], minmax[i + 1]);
            last_start = i;
            continue;
        }
        if((*(intervals.back().second) - (*(intervals.back().first))) + (*minmax[i + 1] - *minmax[i]) - fee < (*minmax[i + 1] - (*(intervals.back().first)))) {
            // intervals.back().second = minmax[i + 1];
            intervals.back().second = *minmax[i + 1] > *(intervals.back().second) ? minmax[i + 1] : intervals.back().second;
            intervals.back().first = *minmax[i] < *(intervals.back().first) ? minmax[i] : intervals.back().first;
        } else {
            intervals.emplace_back(minmax[i], minmax[i + 1]);
            last_start = i;
        }
    }
    int maxdist = 0;
    for(const auto &p : intervals) {
        if(*p.second - *p.first > fee)
            maxdist += (*p.second - *p.first) - fee;
    }
    return maxdist;
    }
};
73403