It's a stupid question, no need for DP

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

  • 0

    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

    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.