It's a stupid question, no need for DP


  • -5
    P
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX, ans = 0;
        for (auto num: prices)
            if (num < minPrice)
                minPrice = num;
            else
                ans = max(num-minPrice,ans);
        return ans;
    }

  • 0
    J

    In your algorithm, it actually defines a sub-problem:

    say f(i) represents the max profit for prices[0] to prices[i]

    f(i + 1) = max(f(i), price[i+1] - minPrice)

    that is a DP idea i think


  • 0
    P

    Yes, you might be right. But in you view, the problem of finding the maximum value of an array is also DP. Nevertheless, I think it's trivial.


Log in to reply
 

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