题目描述

只能进行一次交易（买+卖），要求使利润最大。输出这个最大利润

样例

[7,1,5,3,6,4]
Output: 5

算法1

(DP 贪心) $O(n)$

C++ 代码

int maxProfit(vector<int> &prices) {
    int maxPro = 0;
    int minPrice = INT_MAX;
    for(int i = 0; i < prices.size(); i++){
        minPrice = min(minPrice, prices[i]);
        maxPro = max(maxPro, prices[i] - minPrice);
    }
    return maxPro;
}

Kadane’s Algorithm

更通用版本
计算prices[i] - prices[i-1] 然后找到一个连续含利润最大值的子数列，
如果maxCur 小于0，重置到0。
1. calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array,
2. and find a contiguous subarray giving maximum profit.
3. If the difference falls below 0, reset it to zero.

int maxProfit(vector<int> &prices) {
        int maxCur = 0, maxSoFar = 0;
        for(int i = 1; i < prices.size(); i++) {
            maxCur = max(0, maxCur += prices[i] - prices[i-1]);
            maxSoFar = max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }