Greedy solution in O(n log n) with explanation


  • 2
    T

    Not as fast as dynamic solution but I didn't see it anywhere.

    class Solution {
    public:
        int maxProfit(int K, vector<int>& prices) {
            if(!K)
                return 0;
            vector<int> t;
            for(int i=0, j=0; i<prices.size(); i++)
            {
                if(j == 0 && (i == prices.size()-1 || prices[i+1] > prices[i])
                || j == 1 && (i == prices.size()-1 || prices[i+1] < prices[i]))
                {
                    t.push_back(prices[i]);
                    j = !j;
                }
            }
            int n = t.size() - t.size() % 2;
            int pre[n]; pre[0] = -1;
            int suiv[n]; suiv[n-1] = -1;
            set<pair<int, pair<int, int>>> s;
            for(int i=1; i<n; i++)
            {
                s.insert({abs(t[i]-t[i-1]), {i-1, i}});
                pre[i] = i-1;
                suiv[i-1] = i;
            }
            int r = 0;
            while(!s.empty())
            {
                auto p = s.begin()->second;
                int j = p.first, k = p.second;
                int i = pre[p.first], l = suiv[p.second];
                if(s.size() <= 2*K-1)
                    r += s.begin()->first;
                s.erase(s.begin());
                if(i != -1)
                {
                    s.erase(s.find({abs(t[j] - t[i]), {i, j}}));
                    suiv[i] = l;
                }
                if(l != -1)
                {
                    s.erase(s.find({abs(t[l] - t[k]), {k, l}}));
                    pre[l] = i;
                }
                if(i != -1 && l != -1)
                    s.insert({abs(t[l] - t[i]), {i, l}});
            }
            return r;
        }
    };
    

    We process in two steps:

    • Firstly, we remove all the noise. For example, [1,2,3,4,3,2,4,5] becomes [1, 4, 2, 5].
    • Secondly, a O(n^2) solution consists in erasing at each iteration the neighbors with the smallest absolute difference (in the example above, it's [4, 2]). To reduce the cost from O(n^2) to O(log n), we use a set, containing all absolute differences as well as indices corresponding to this differences. When we erase (i, j), we also have to erase (pre[i], i) and (j, next[j]), where pre[i] is the remaining indice preceding i and next[j] is the remaining indice following j, and we also have to add (pre[i], next[j]).

  • 0
    D

    @Thomas_94 For input case 3 8 1 100, it looks like we can't erase 8 1. Could you explain a little about your choice of the smallest absolute difference?


  • 0
    T

    @dachuan.huang The idea of erase the smallest absolute differences is to let at the end only the K choosen transactions.
    With 3 8 1 100, if k <= 2 (which can be seen as k = 1), we first erase 3 and 8 (|3 - 8| < |8 - 1| and |3 - 8| < |1 - 100|). It remains 1 and 100.

    Note that when you have (ai, ai+1, ai+2, ai+3) such that the smallest absolute difference of the list is |ai+1 - ai+2|, after erasing (ai+1, ai+2), you will not loose in total 3 * |ai+1 - ai+2| (up down and up or down up and down) but 2 * |ai+1 - ai+2|, because as |ai+1 - ai+2| is the smallest absolute difference, you can "find" it in its neighbors: (ai+1, ai+2) is "contained" in (ai, ai+3).


  • 0

    why is s.size()<=2*K-1? Isnt it we need k transactions?


  • 0
    T

    @kondaramakrishna99gmail.com To be quick, because most of the time s.size() decrease by two (three elements erased, one added).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.