LeetCode刷题实战122：买卖股票的最佳时机 II-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 买卖股票的最佳时机 II，我们先来看题面：

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

Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

题意

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

样例

解题

https://www.cnblogs.com/gzshan/p/11114182.html

本题和上一题相比，唯一的区别是：这里对买卖次数没有限制。

这里我们可以采用贪心策略来解决：首先我们需要理解一点，第i天买入，第j天卖出得到的收益和第i天买入，第i+p天卖出，第i+p天再买入，第j天卖出得到的收益是相同的。比如[1,2,3,4,5]，很明显我们知道最大收益是4，可以看作是第一天买入，第五天卖出，但是也可以看作是第1天买入，第二天卖出，同时买入，第三天又卖出，同时买入······

理解了这一点，我们就清楚这里为什么能用贪心的思想了，从第一天开始买入，只要有收益就可以直接卖出，接下来再买入，同样一旦有收益就可以卖出，这是一种典型的贪心思想，局部最优达到全局最优。

从代码角度来说，我们只需要累加后一天和前一天的差（后一天大于前一天的情下）即可。

public int maxProfit(int[] prices) {
        //贪心法
        if(prices==null || prices.length==0)
            return 0;
        int profit=0;
        for(int i=1;i            if(prices[i]>prices[i-1])
                profit+=(prices[i]-prices[i-1]);
        }
        return profit;
    }

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

上期推文：

LeetCode1-120题汇总，希望对你有点帮助！

LeetCode刷题实战121：买卖股票的最佳时机

​LeetCode刷题实战122：买卖股票的最佳时机 II

题意

解题

LeetCode刷题实战122：买卖股票的最佳时机 II