Leetcode第121题到123题连续出现了三道买卖股票相关的题目，一年前的网易笔试和半年前的百度面试都遇到过121题，不过不用慌，看完本文，你一定能够完美解决买卖股票的问题。那么我们由易到难，依次介绍这三道题目。
121. Best Time to Buy and Sell Stock
121题题目是这样的：
在所有的过程中，我们只允许一次的买卖，基于这个问题，我们得到了下面的两种解法。
解法1
根据题意，我们只需要找出数组中最大的差值即可，即 max(prices[j] – prices[i]) ，i < j。
如何得到最大的差值，只需要一次遍历即可，在遍历的用一个变量记录遍历到当前时的最小值即可。时间复杂度为O(n).
相关的实现代码如下：
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int min = prices[0];
int profit = 0;
// 第i天的价格可以看作是买入价也可以看作是卖出价
for (int i = 1; i < prices.length; i++) {
// 找到更低的买入价
if (min > prices[i]) {
// 更新买入价
min = prices[I];
}
// 当天的价格不低于买入价
else {
// 如果当天买出的价格比之前卖出的价格高
if (profit < prices[i] - min) {
// 更新卖出价
profit = prices[i] - min;
}
}
}
return profit;
}
}
解法2
第二题的解法是我在面试百度的时候想到的，应用的是求数组中和最大的连续子数组序列的思路，这种思路又被称为Kadane's Algorithm。我们有两个问题：
如何转化为求数组中的和最大的连续子序列？相邻两个数作差即可，这样的话子序列的和就是我们在子序列开始卖出股票，在子序列最后买回股票所能得到的收益。
那么什么是Kadane's Algorithm呢？
kadane算法利用了数学归纳法的思想。简单来讲就是，随意给你一个现成的数组，比如说−2, 1, −3, 4, −1, 2, 1, −5, 4，让你求其中的最大子列和，并不是容易的事情。但如果我们能从第一个数开始，随着数组的扩充，始终对其最大子列和保持跟踪，就可以轻易的求出任意一个数组的最大子列和。换言之，长度n的数组我们不会求，长度为一的总能算出来吧？长度为一的算出来了，二也就能算出来，二算出来了，三就能算出来，以此类推，用这种根据i求i+1的思想，我们就能达到最终目的。
详细的分析一下，往一个长度为i的数组后面插入第i+1个数，这时，数组的最大子列只有两种情况，要么包括第i+1个数，要么不包括第i+1个数。即：
maxsubarraum = max(以第i+1个数结尾的子列和， 不以第i+1个数结尾的子列和)。*
先计算前者，以第i+1个数结尾的子列和怎么算呢？很简单，要么它是以第i个数结尾的子列作为前缀，要么它不以之作为前缀。假设第i+1个数为x，那么：
以第i+1个数结尾的子列和 = max(x，以第i个数结尾的子列和+x) (1)。
再计算后者，也就是不以第i+1个数结尾的子列和。这啥意思呢？其实就是插入第i+1个数之前的数组的最大子列和嘛。我们的数学归纳思想也就体现在这里，如果你还看不明白，我们将*式改写：
数列长度i+1的最大子列和 = max(以第i+1个数结尾的子列和， 数列长度i的最大子列和)。(2)
看到了吧，无论(1)式还是(2)式，后一种情况都可以由前一种情况推出，妥妥的数学归纳。我们的算法只要从i=1开始，一步一步按照上面的规则走下去，那么任意一个数列的最大子列和就能求出来了！
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2)
return 0;
int maxCur = 0;
int maxSoFar = 0;
for(int i=1;i<prices.length;i++){
maxCur = Math.max(0,Math.max(prices[i]-prices[i-1],maxCur + prices[i] - prices[i-1]));
maxSoFar = Math.max(maxCur,maxSoFar);
}
return maxSoFar;
}
}
122. Best Time to Buy and Sell Stock II
这道题的描述如下：
这道题允许无限次的买卖，简直太简单了吧，只要后一天的价值比前一天的大，那就买卖呗。不忍吐槽的一道题，代码如下：
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2)
return 0;
int maxProf = 0;
for(int i = 1;i<prices.length;i++){
maxProf += (prices[i] > prices[i-1] ? prices[i] - prices[i-1]:0);
}
return maxProf;
}
}
123. Best Time to Buy and Sell Stock III
这一题还是比较难的，题目描述如下：
我们只允许最多两次的买卖，这可如何是好？我们同样提供两种思路：
解法1
这个问题可以转换成Best Time to Buy and Sell Stock I问题。
两次股票交易的核心是可以定义一个交易点，在这个交易点之前可以做一次交易(赚的最大数目的钱为firstProf)，在这个交易点之后可以做一个交易(赚的最大数目的钱是secondProf)。那么要求的是max(firstProf+secondProf)。但是这个方法的时间复杂度是O(N^2)，空间复杂度是O(1)。leetcode中显示超时。
可以使用两次扫描的方法避免上面的双重循环。
不同于Best Time to Buy and Sell Stock I中定义的初始状态A[i]表示第i天卖出挣的最大数目的钱，这个更进一步直接定义A[i]表示前i天赚的最大数目的钱。minPrice表示从第0天到第i-1天中的最低价格。
A[0]=0。（初始状态）
A[1]=max(prices[1]-prices[0],A[0])
A[2]=max(prices[2]-minPrice,A[1])
.....
即A[i]=max(price[i]-minPrice,A[i-1]).
另外一次扫描从数组后向前扫描，定义B[i]表示从第i天到最后一天n能赚的最大数目的钱。maxPrice表示第i+1天到n天的最高价格。
B[n]=0。（初始状态）
B[n-1]=max(maxPrice-prices[n-1],B[n])
B[n-2]=max(maxPrice-prices[n-2],B[n-1])
.....
即B[i]=max(maxPrice-prices[i],B[i+1])
那么以第i天为分割点能赚的最多数目的钱为A[i]+B[i]
问题的解为max{A[i]+B[i]}。0<=i<=n。
时间复杂度是O(N)，空间复杂度是O(N)。
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2)
return 0;
int[] asc = new int[prices.length];
int[] desc = new int[prices.length];
int n = prices.length;
int minprice = prices[0];
int maxProf = 0;
asc[0] = 0;
for(int i=1;i<n;i++){
asc[i] = Math.max(prices[i] - minprice,maxProf);
minprice = Math.min(prices[i],minprice);
maxProf = asc[i];
}
desc[prices.length-1] = 0;
maxProf = 0;
int maxprice = prices[prices.length-1];
for(int i=prices.length-2;i>=0;i--){
desc[i] = Math.max(maxprice-prices[i],maxProf);
maxprice = Math.max(maxprice,prices[i]);
maxProf = desc[i];
}
maxProf = 0;
for(int i=0;i<prices.length;i++){
maxProf = Math.max(maxProf,asc[i] + desc[i]);
}
return maxProf;
}
}
解法2
第二种解法的核心是假设手上最开始只有0元钱，那么如果买入股票的价格为price，手上的钱需要减去这个price，如果卖出股票的价格为price，手上的钱需要加上这个price。
因此我们定义了4个状态：
Buy1[i]表示前i天做第一笔交易买入股票后剩下的最多的钱；
Sell1[i]表示前i天做第一笔交易卖出股票后剩下的最多的钱；
Buy2[i]表示前i天做第二笔交易买入股票后剩下的最多的钱；
Sell2[i]表示前i天做第二笔交易卖出股票后剩下的最多的钱；
那么假设我们在第i天时第二次卖出股票，我们卖出股票可以获得Buy2[i-1]+prices[i]的钱，假设在第i天前已经完成了两笔交易，那么我们最多的钱是Sell2[i-1]，因此
Sell2[i]=max{Sell2[i-1],Buy2[i-1]+prices[I]}
同样的道理，假设我们在第i天时第二次买入股票，我们手中的钱是Sell[i-1]-prices[i]，假设我们在第i天钱已经卖出了两次股票，那么我们最多的钱是Buy2[i-1]，因此
Buy2[i]=max{Buy2[i-1],Sell[i-1]-prices[I]}
同样的道理我们还可以得到：
Sell1[i]=max{Sell[i-1],Buy1[i-1]+prices[I]}
Buy1[i]=max{Buy[i-1],-prices[I]}
可以发现上面四个状态都是只与前一个状态有关，所以可以不使用数组而是使用变量来存储即可。
这是leetcode中的讨论网址：https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2)
return 0;
int sell2 = 0;
int sell1 = 0;
int buy1 = Integer.MIN_VALUE;
int buy2 = Integer.MIN_VALUE;
for(int i =0;i<prices.length;i++){
sell2 = Math.max(sell2,buy2+prices[i]);
buy2 = Math.max(buy2,sell1-prices[i]);
sell1 = Math.max(sell1,buy1+prices[i]);
buy1 = Math.max(buy1,-prices[i]);
}
return sell2;
}
}
参考文献
1、从一道easy leetcode问题，谈谈最大子列和的Kadane算法：http://blog.csdn.net/The__Apollo/article/details/77367534
2、LeetCode123:Best Time to Buy and Sell Stock III：http://blog.csdn.net/u012501459/article/details/46514309
