题目描述

121. 买卖股票的最佳时机

样例

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

解题思路

状态表示

dp[i], 表示在第i天时候, 交易最大的利润有多少.

状态转移方程

dp[i] = max(dp[i-1], prices[i] - minVal), 其中 minVal 是[0, i-1]上 prices的最小值.
同时, 需要维持minVal的值.

时间复杂度: $O(n)$

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        if (!n || n == 1)  return 0;

        vector<int> dp(n, 0);

        int minVal = prices[0];
        for (int i = 1; i < n; ++i)
        {
            minVal = min(minVal, prices[i-1]);
            cout << "minVal: " << minVal << endl;
            dp[i] = max(dp[i-1], prices[i] - minVal);
        }

        return dp[n-1];
    }
};