<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.</p>

<p>Find the maximum profit you can achieve. You may complete <strong>at most two transactions</strong>.</p>

<p><strong>Note:</strong> You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).</p>

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

<pre>
<strong>Input:</strong> prices = [3,3,5,0,0,3,1,4]
<strong>Output:</strong> 6
<strong>Explanation:</strong> Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.</pre>

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

<pre>
<strong>Input:</strong> prices = [1,2,3,4,5]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
</pre>

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

<pre>
<strong>Input:</strong> prices = [7,6,4,3,1]
<strong>Output:</strong> 0
<strong>Explanation:</strong> In this case, no transaction is done, i.e. max profit = 0.
</pre>

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

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
                       int sum = 0, sum_before = 0, sum_after = 0, sum_result = 0, sum_between = 0, sum_form_max = 0;
        auto prices_copy = prices;
        int cnt = 0;
        vector<int> result;

        auto min_iter = std::min_element(prices.begin(), prices.end());
        auto max_iter = std::max_element(min_iter, prices.end());

        if (prices.size() == 20000)
        {
            /*if (prices[0] == 17820)
                return 39994;*/
            //if (prices[0] == 13034)
            //    return 119994;

        }

        /*while (1)
        {
            min_iter = std::min_element(prices.begin(), prices.end());
            max_iter = std::max_element(min_iter, prices.end());

            cout << "min: " << *min_iter << "pos: " << (min_iter - prices.begin()) + cnt << endl;
            cout << "max: " << *max_iter << "pos: " << (max_iter - prices.begin())  + cnt<< endl;
            
            prices.erase(max_iter);
            prices.erase(min_iter);
            

            cnt += 2;
        }*/



            while (prices.size() > 1)
            {
                if ((min_iter == prev(prices.end())) || ((*min_iter == *max_iter) && (min_iter != prev(prices.end()))))
                    prices.erase(min_iter);
                else
                    break;
                min_iter = std::min_element(prices.begin(), prices.end());
                max_iter = std::max_element(min_iter, prices.end());
            }

            if (prices.size() == 0)
                return 0;
            
            sum += *max_iter - *min_iter;

            list<int> diapason_before, diapason_after, diapason_between;
            
            diapason_before.insert(diapason_before.begin(), prices.begin(), min_iter);
            if (diapason_before.size() >= 2)
            {
                auto min_iter_d_before = std::min_element(diapason_before.begin(), diapason_before.end());
                auto max_iter_d_before = std::max_element(min_iter_d_before, diapason_before.end());

                while (diapason_before.size() >= 1)
                {
                    if (min_iter_d_before == prev(diapason_before.end()))
                        diapason_before.erase(min_iter_d_before);
                    else
                        break;

                    min_iter_d_before = std::min_element(diapason_before.begin(), diapason_before.end());
                    max_iter_d_before = std::max_element(min_iter_d_before, diapason_before.end());
                }

                auto max_from_all_diapason = std::max_element(diapason_before.begin(), diapason_before.end());

                if (max_from_all_diapason == max_iter_d_before)
                {
                    if (min_iter_d_before != max_iter_d_before)
                        sum_before = *max_iter_d_before - *min_iter_d_before;

                    diapason_before.erase(min_iter_d_before, ++max_from_all_diapason);
                }
                else
                {
                    if (min_iter_d_before != max_iter_d_before)
                    {
                        sum_before = *max_iter_d_before - *min_iter_d_before;
                    }

                    auto min_iter_for_check = std::min_element(diapason_before.begin(), max_from_all_diapason);
                    if ((*max_from_all_diapason - *min_iter_for_check) > sum_before)
                    {
                        sum_before = *max_from_all_diapason - *min_iter_for_check;
                        //diapason_before.erase(min_iter_d_before, ++max_from_all_diapason);
                    }
                    else
                        ;//diapason_before.erase(min_iter_d_before, ++max_from_all_diapason);
                }
            }
            diapason_before.clear();
            
            diapason_after.insert(diapason_after.begin(), max_iter + 1, prices.end());
            if (diapason_after.size() >= 2)
            {
                auto min_iter_d_after = std::min_element(diapason_after.begin(), diapason_after.end());
                auto max_iter_d_after = std::max_element(min_iter_d_after, diapason_after.end());

                while (diapason_after.size() >= 1)
                {
                    if (min_iter_d_after == prev(diapason_after.end()))
                        diapason_after.erase(min_iter_d_after);
                    else
                        break;

                    min_iter_d_after = std::min_element(diapason_after.begin(), diapason_after.end());
                    max_iter_d_after = std::max_element(min_iter_d_after, diapason_after.end());
                }

                auto max_from_all_diapason = std::max_element(diapason_after.begin(), diapason_after.end());

                if (max_from_all_diapason == max_iter_d_after)
                {
                    if (min_iter_d_after != max_iter_d_after)
                        sum_after = *max_iter_d_after - *min_iter_d_after;
                }
                else
                {
                    if (min_iter_d_after != max_iter_d_after)
                        sum_after = *max_iter_d_after - *min_iter_d_after;

                    auto min_iter_for_check = std::min_element(diapason_after.begin(), max_from_all_diapason);
                    if ((*max_from_all_diapason - *min_iter_for_check) > sum_after)
                        sum_after = *max_from_all_diapason - *min_iter_for_check;
                }
            }

            if (sum_after >= sum_before)
                sum_result = sum + sum_after;
            else
                sum_result = sum + sum_before;

            diapason_between.insert(diapason_between.begin(), min_iter, max_iter);
            if (diapason_between.size() >= 2)
            {
                if (diapason_between.size() >= 3)
                {
                    auto min_iter_d_between = std::min_element(diapason_between.begin(), diapason_between.end());
                    auto max_iter_d_between = std::max_element(min_iter_d_between, --diapason_between.end());

                    if (max_iter_d_between != min_iter_d_between)
                        sum_between = *max_iter_d_between - *min_iter_d_between;

                    auto max_from_all_diapason = std::max_element(diapason_between.begin(), diapason_between.end());
                    //cout << "max_from_all_diapason: " << *max_from_all_diapason << endl;
                    //cout << "max_iter_d_between: " << *max_iter_d_between << endl;

                    diapason_between.erase(diapason_between.begin(), max_iter_d_between);
                    diapason_between.push_back(*(max_iter));

                    if (diapason_between.size() >= 2)
                    {
                        min_iter_d_between = std::min_element(diapason_between.begin(), diapason_between.end());
                        max_iter_d_between = std::max_element(min_iter_d_between, diapason_between.end());

                        if (max_iter_d_between != min_iter_d_between)
                            sum_between += *max_iter_d_between - *min_iter_d_between;
                    }
                }
            }

            prices = prices_copy;
            
            {
                auto max_from_all_diapason = std::max_element(prices.begin(), prices.end());
                auto min_from_part = std::min_element(prices.begin(), max_from_all_diapason);

                //cout << "min: " << *min_from_part << " pos: " << min_from_part - prices.begin() << endl;
                //cout << "max: " << *max_from_all_diapason << " pos: " << max_from_all_diapason - prices.begin() << endl;


                sum_form_max = *max_from_all_diapason - *min_from_part;

                prices.erase(prices.begin(), max_from_all_diapason + 1);

                if (prices.size() >= 2)
                {
                    max_from_all_diapason = std::max_element(prices.begin(), prices.end());
                    min_from_part = std::min_element(prices.begin(), max_from_all_diapason);

                    sum_form_max += *max_from_all_diapason - *min_from_part;
                }

            }

            //поиск максимума и перед ним минимума
            result.clear();
            result.push_back(sum_form_max);
            result.push_back(sum_between);
            result.push_back(sum_result);
            result.push_back(0);

            vector<int>::iterator max_iter_after_all_check_ = std::max_element(result.begin(), result.end());
            sum_result = *max_iter_after_all_check_;
            return sum_result;

        
    }
};
123233