1. 交易股票的最佳时机

（以下均疏忽暴力求解）

一次遍历

策略：

既然只有一次交易，那么能够通过遍从来寻找最大的差值

过程：

graph TD
应用数组一一存储元素-->寻找前面元素的最低值-->更新并存储其差值

工夫复杂度：O(n)
空间复杂度：O(1)

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

2. 交易股票的最佳时机 II

贪婪算法

策略：

• 隔日上涨：明天买入，今天卖出
• 多日上涨：持有股票到最高点再卖出
• 隔日 / 多日上涨：不交易

graph TD
遍历数组-->若数值递增则直至上涨的前一天卖出-->若数值递加则不交易-->统计利润总值

工夫复杂度：O(n)
空间复杂度：O(1)

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            int tmp = prices[i] - prices[i - 1];
            if (tmp > 0) profit += tmp;
        }
        return profit;
    }
}

3. 交易股票的最佳时机 III

工夫复杂度：O(n)
空间复杂度：O(1)

var maxProfit = function(prices) {
    const n = prices.length;
    let buy1 = -prices[0], buy2 = -prices[0];
    let sell1 = 0, sell2 = 0;
    for (let i = 1; i < n; i++) {
        buy1 = Math.max(buy1, -prices[i]);
        sell1 = Math.max(sell1, buy1 + prices[i]);
        buy2 = Math.max(buy2, sell1 - prices[i]);
        sell2 = Math.max(sell2, buy2 + prices[i]);
    }
    return sell2;
};

4. 交易股票的最佳时机 IV

5. 最佳交易股票机会含冷冻期

6. 交易股票的最佳时机含手续费