【贪心算法】之 买股票的最佳时机（中等题）

1.买卖股票的最佳时机

把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！

那么只收集正利润就是贪心所贪的地方！

局部最优：收集每天的正利润，全局最优：求得最大利润。

局部最优可以推出全局最优，找不出反例，试一试贪心！

public static int maxProfit(int[] prices) {
        int sum = 0;
        int temp;
        for (int i = 0; i < prices.length - 1; i++) {
            temp = prices[i + 1] - prices[i];
            if (temp > 0) {
                sum += temp;
            }
        }
        return sum;
    }

2.买卖股票的最佳时机含手续费

在贪心算法：122.买卖股票的最佳时机II 中使用贪心策略不用关心具体什么时候买卖，只要收集每天的正利润，最后稳稳的就是最大利润了；

而本题有了手续费，就要关系什么时候买卖了，因为计算所获得利润，需要考虑买卖利润可能不足以手续费的情况。

当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利。

//买卖股票的最佳时机含手续费
public class leetcode_714 {
    public static void main(String[] args) {
        int[] prices={1,4,3,8,4,9};
        //1买4卖 8卖 4买 9卖
        int fee=2;
        System.out.println(maxProfit(prices, fee));
    }

    public static int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int buy = prices[0] + fee;
        int profit = 0;
        for (int i = 1; i < n; ++i) {
            if (prices[i] + fee < buy) {
                buy = prices[i] + fee;
            } else if (prices[i] > buy) {
                profit += prices[i] - buy;
                buy = prices[i];//在4卖出去，相当于我们买了4又没花手续费
            }
        }
        return profit;
    }
}