Problem

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

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.:

问题描述

给定一个股票每天的售价，如果你可以完成任意多次交易，求最大的收益。注意，你必须要卖出股票才能买入新的股票。

样例

输入: [7, 1, 5, 3, 6, 4]
输出: 7
解释: 在第二天买入并在第三天卖出，收益为 4，在第四天买入并在第五天卖出，收益为 3，总收益为 7。

解法 1

由于可以完成任意多次交易，那么，我们就可以不用记录当前完成交易的次数。但题目中有一个要求，在手上持有股票时，比如卖出股票才能买入新的股票。那么，我们用两个数组 f、g 来保留中间结果。f[i] 表示第 i+1 天时手上持有股票时的最大收益，g[i] 表示第 i+1 天时手上不持有股票时的最大收益。最后返回 g[n-1] 即可。

我们考虑如何计算 f[i] 和 g[i]:

• f[i] 表示第 i+1 天手上持有股票的最大收益，有两种可能情形:
  • 第 i 天持有股票，则第 i+1 天不卖出股票，此时最大收益为 f[i-1]
  • 第 i 天不持有股票，第第 i+1 天必须得买入股票，此时最大收益为 g[i-1]-prices[i]
  • 故 f[i]=max(f[i-1], g[i-1]-prices[i])
• g[i] 表示第 i+1 天手上不持有股票的最大收益，有两种可能情形:
  • 第 i 天不持有股票，第第 i+1 天不买入股票，此时最大收益为 g[i-1]
  • 第 i 天持有股票，则第 i+1 天卖出股票，此时最大收益为 f[i-1]+prices[i]
  • 故 g[i]=max(g[i-1], f[i-1]+prices[i])

参考代码: