p309

发表于 | 分类于 |

LeetCode p309 Best Time to Buy and Sell Stock with Cooldown 题解

1.题目：

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) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

题意：

输入一个数组，记录每天一个股票的市值，你可以在每天选择买入卖出。
求可以赚到的最多的钱。
注意：卖出之前先要买入。卖出之后隔一天才能够买入。

2.解题思路:

p1表示当天是卖出的，p2表示不做操作。
p1的值为头一天进行卖出操作：p1 - prices[i - 1] + prices[i] （把卖出的买回来等于没操作）
头一天没操作p2.
p2在头一天的可能情况中取大值，且不进行操作。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
public class Solution {
    public int maxProfit(int[] prices) {
        int p1 = 0;// sell
		int p2 = 0;// nothing

		for (int i = 1; i < prices.length; i++) {
			int c = p1;
			p1 = Math.max(p2, p1 - prices[i - 1] + prices[i]);
			p2 = Math.max(c, p2);
		}
		return Math.max(p1, p2);
    }
}

4.一些总结：