c++ solution with explanation


  • 0
    C

    This is my first accepted solution on DP problem, I'm so thrill.

    Let's see

    [5, 7, 2, 6] => 4;
    [5, 7, 6, 9] => 3;
    [5, 8, 1, 2] => 3;

    So simply, we can draw that the subarray after the min num, have the possibility the make the max profit.
    Now we have the state: the max profit res and the index of the min num of the array li.

    '''
    int maxProfit(vector<int>& prices) {
    int res = 0;
    int li = 0;
    for (int i=1; i<prices.size(); i++) {
    res = max(prices[i] - prices[li], res);
    li = prices[i] < prices[li] ? i : li;
    }
    return res;
    }
    '''


Log in to reply
 

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