05 August 2008
Say you have an array for which the i_th 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:
1
2
3
4
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:
1
2
3
4
5
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:
1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
这道题跟121 Best Time to Buy and Sell Stock相比，可以无限购买。股票系列原始状态转移方程，三个维度分别是 天数-可以交易k次-是否持有股票：
今天不持有股票： dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
今天持有股票： dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
这道题数组中的 k 是无限次可交易，不会改变了，也就是说不需要记录 k 这个状态了，所以状态转移方程为：
今天不持有股票： dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
今天持有股票： dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int maxProfit(int[] prices) {
int day = prices.length;
if (day <= 1) {
return 0;
}
// dp[][]表示利润，两个维度表示天数和是否有股票，0表示没有，1表示有
int[][] dp = new int[day][2];
dp[0][0] = 0; // 第1天，手中无股票
dp[0][1] = -prices[0]; // 第1天手中有股票（在第1天买入）
for (int i = 1; i < day; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[day - 1][0]; //最后卖出股票肯定比没卖出股票(dp[day - 1][0])利润要大
}
}
考虑状态压缩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (prices.length <= 1) {
return 0;
}
int lastBuy = -prices[0];
int lastSell = 0;
for (int i = 1; i < len; i++) {
int curBuy = Math.max(lastBuy, lastSell - prices[i]);
int curSell = Math.max(lastSell, lastBuy + prices[i]);
lastBuy = curBuy;
lastSell = curSell;
}
return lastSell;
}
}
直接计算，从第二天开始算，如果当前的股票价格高于前一日的话，就把差额利润算入到结果当中，如果后面的值更高，那继续把利润加入；虽然例子中说了不能卖了再买，但是如上算法的利润是一样的，所以只需遍历数组，然后把每个数和它后面的数进行比较即可。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int maxProfit(int[] prices) {
int result = 0;
for (int i = 0; i < prices.length - 1; i++) {//到倒数第二个数为止
if (prices[i] < prices[i+1]) {
result += prices[i+1] - prices[i];
}
}
return result;
}
}