【贪心算法】买卖股票的最佳时机

不管前方的路有多苦，只要走的方向正确，不管多么崎岖不平，都比站在原地更接近幸福。 —— 千与千寻

一、题目描述

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。返回你能获得的最大利润 。

示例：

来源：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii

二、 思路

本题是一道典型的贪心算法解决的题目，贪心算法最难想的就是如何贪心，也就是我们贪的到底是什么，对本题来说，可以计算出每个相邻天买入卖出股票可获得的利润，取出所有的正利润就是最优的购买方案，此时能获得的总利润也是最大的。也就是说，我们贪心贪的就是所有能获得正利润的日子，因为如果选了负利润的日子，那么结果一定会变小。

三、代码

    public int maxProfit(int[] prices) {
    
        // 定义额外 profit 数组表示当天利润
//        int len = prices.length;
//        int[] profit = new int[len-1];
//        int ans = 0;
//        for(int i=1; i<len; i++){
//            profit[i] = prices[i] - prices[i-1];
//        }
//        for(int i=0; i<len-1; i++){
//            ans += profit[i]>0 ? profit[i] : 0;
//        }
//        return ans;
               
        // 不定义额外 profit 数组   
        int len = prices.length;
        int ans = 0;
        for(int i=1; i<len; i++){
            int profit = prices[i] - prices[i-1];
            ans += (profit > 0) ? profit : 0;
        }
        return ans;
    }

四、总结

贪心算法没有具体套路，还是比较难想到的，但有个总体思路就是找到局部最优解，再由局部最优解找到全局最优解。