题目描述

解法 dp

1.dp数组含义
dp[i]：第i天卖出可获得最大收益
2.dp方程
dp[i] = max(dp[i - 1], price[i] - min(price[0]~price[i])
3.初始值
dp[0] = 0

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) return 0;
        int cMin = prices[0];
        int len = prices.size() - 1;
        vector<int> dp (len + 1, 0);
        for(int i = 1; i <= len; i++) {
            cMin = min(cMin,prices[i]);
            dp[i] = max(dp[i - 1], prices[i] - cMin);
        }
        return dp[len];
    }
};

时间复杂度O(N)
空间复杂度O(N)
优化：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) return 0;
        int cMin = prices[0];
        int ans = 0;
        int len = prices.size() - 1;
        for(int i = 1; i <= len; i++) {
            cMin = min(cMin,prices[i]);
            ans = max(ans, prices[i] - cMin);
        }
        return ans;
    }
};

时间复杂度O(N)
空间复杂度O(1)