leetcode: Best Time to Buy and Sell Stock II

问题描述：

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).

原问题链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

 

问题分析

　　在这个问题的场景里，它和前面的情况有点不同。因为你可以选择在这若干天里买卖若干次。只是每次只能有一个交易，也就是说，每次只能卖一个，买一个。我们可以这么来看，对于价格来说，它后面的价格可能比前面的高，也可能比前面的低。如果要获取最大利益的话，就需要将所有后面比前面高的价格差都获取。对于一个存在有一个或者若干个递增的序列来说，我们可以每次计算一个元素和它前一个元素的差，再把这些差累积起来，这就是它能获取到的最大利益。

　　但是，并不是所有序列都是严格递增的，可能后面的值比前面的小。那么从利益最大化来说，它就应该不能卖，也就是说，当前的利益值为0。这样，我们可以在一个循环里，计算当前元素和前一个元素的差值，并取它和0之间最大的那个累加到结果中。这样得到的就是最终的最大利润值。

　　详细代码实现如下：

 

public class Solution {
    public int maxProfit(int[] prices) {
        int price = 0, result = 0;
        for(int i = 1; i < prices.length; i++) {
            result += Math.max(price, prices[i] - prices[i - 1]);
        }
        return result;
    }
}