题目

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

设计一个算法来找到最大的利润。你可以完成尽可能多的交易（多次买卖股票）。然而，你不能同时参与多个交易（你必须在再次购买前出售股票）。

Say you have an array 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 (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

解题方法

这是一道非常简单的题，只需要考虑到股票价格在波动中会有多个峰值和谷值，我们只需要在谷值购入股票，峰值时出售股票，即可获得最大利润，从而成为超越巴菲特的股市大佬，然而题目中每天股价是已知的，这种条件在现实中是不存在的，所以想想就好。

通过一个O(n)循环，比较后一天股价与今天股价的大小，如果比今天大，最大利润就加上这两天的差价，相当于持有了一天股票升值；如果比今天小，则直接进入下一次循环，相当于今天抛了已购股票(成功割取当天的韭菜)，如果处于没有购买股票的状态，则相当于继续观望了一天。时间复杂度为O(n)，跑了1ms，超过99.89%的Java提交。

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

结语

长风破浪会有时，直挂云帆济沧海。Keep coding！

这是笔者刷leetcode的开始，代码都托管在我的Github上，有兴趣的朋友可以相互交流，请多多指教。