Best Time to Buy and Sell Stock I

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

双指针法

复杂度

时间 O(N) 空间 O(1)

思路

根据买卖股票的特性，我们必须先低价买，再高价卖，这个找最大收益的过程实际上是找到目前为之的最低价。在遍历价格数组时，根据这个动态更新的最低价和当前的价格可以算出当前卖股票最大能赚多少钱。

代码

public class Solution {    public int maxProfit(int[] prices) {        int min = Integer.MAX_VALUE, res = 0;        for(int i = 0 ; i < prices.length; i++){if(prices[i]<min) min = prices[i];if((prices[i]-min)>res) res = prices[i] - min;        }        return res;    }}

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

贪心法

复杂度

时间 O(N) 空间 O(1)

思路

既然能买卖任意次，那最大收益的方法就是尽可能多的低入高抛。只要明天比今天价格高，就应该今天买入明天再卖出。

代码

public class Solution {    public int maxProfit(int[] prices) {        int sum = 0;        for(int i = 1; i < prices.length; i++){if(prices[i]>prices[i-1]) sum += prices[i] - prices[i-1];        }        return sum;    }}

Best Time to Buy and Sell Stock III

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 at most two transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

双向动态规划

复杂度

时间 O(N) 空间 O(N)

思路

最简单的方法就是对每一个时间点，将其所有两边的数组都执行一次Best Time to Buy and Sell Stock I的解法，但这会带来O(N^2)的时间复杂度。实际上当计算prices[0]到prices[i]的最大收益时，我们已经计算过prices[0]到prices[i-1]的最大收益了，我们可以利用这个之前计算的结果降低时间复杂度（不过代价是额外空间），所以需要把prices[0]到prices[i]的最大收益存在left[i]数组中。具体解法和I是一样的，也是维护一个前半段最小值。

分别得出以i点为分割点，左半段最大收益的数组left，和右半段最大收益的数组right后，我们就可以遍历一遍这两个数组，找出最大的left+right组合。实际上，该解法就是将I的解法双向各执行一遍并记录结果。

代码

public class Solution {    public int maxProfit(int[] prices) {        if(prices.length == 0) return 0;        int[] left = new int[prices.length];        int[] right = new int[prices.length];        int leftMin = prices[0];        int rightMax = prices[prices.length-1];        int sum = 0;        //计算左半段最大收益        for(int i = 1 ; i < prices.length; i++){leftMin = Math.min(prices[i], leftMin);left[i] = Math.max(prices[i] - leftMin, left[i-1]);        }        //计算右半段最大收益        for(int i = prices.length - 2 ; i >= 0; i--){rightMax = Math.max(prices[i], rightMax);right[i] = Math.max(rightMax - prices[i], right[i+1]);        }        //找出两次交易最大收益组合        for(int i = 0 ; i < prices.length; i++){if((left[i]+right[i])>sum) sum = left[i]+right[i];        }        return sum;    }}

滚动扫描法

复杂度

时间 O(N) 空间 O(1)

思路

其实我们并不需要知道每个时间点买卖第一第二笔股票收益的全部信息，我们只要知道前一个时间点买卖第一第二笔股票的最大收益信息，就可以直到当前最大的收益信息了，这样可以为我们省去额外空间。这里我们遍历prices数组的时候，维护四个变量:release2是在该价格点卖出第二笔股票后手里剩的钱，等于上一轮买入第二笔股票后手里剩的钱加上卖出当前股票价格的钱，或者上一轮卖出第二笔股票后手里剩的钱两者中较大的。hold2是在该价格点买入第二笔股票后手里剩的钱，等于上一轮卖出第一笔股票后手里剩的钱减去买入当前股票价格的钱，或者上一轮买入第二笔股票后手里剩的钱两者中较大的。release1是在该价格点卖出第一笔股票后手里剩的钱，等于上一轮买入第一笔股票后手里剩的钱加上卖出当前股票价格的钱，或者上一轮卖出第一笔股票后手里剩的钱两者中较大的。hold1是在该价格点买入第一笔股票后手里剩的钱，等于初始资金减去买入当前股票价格的钱或者初始资金（不买）中较大的。这里计算顺序按照release2 -> hold2 -> release1 -> hold1，因为卖是要后于买的，而第二次交易也是后于第一次交易的，通过这个顺序我们能用这些变量自身来记录上次的值。相当于release2的时间点要先于hold1四个点。

Prices      3    1    2    8    3    1    9    6release2    0    0    1    7    7    7    1    1hold2      -3   -1   -1   -1    4    6    1    1release1    0    0    1    7    7    7    1    1hold1      -3   -1   -1   -1   -1   -1    3    3

代码

public class Solution {    public int maxProfit(int[] prices) {        int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;        int release1 = 0, release2 = 0;        for(int i = 0; i < prices.length; i++){//在该价格点卖出第二笔股票后手里剩的钱，等于上一轮买入第二笔股票后手里剩的钱加上卖出当前股票价格的钱，或者上一轮卖出第二笔股票后手里剩的钱两者中较大的release2 = Math.max(release2, hold2 + prices[i]);//在该价格点买入第二笔股票后手里剩的钱，等于上一轮卖出第一笔股票后手里剩的钱减去买入当前股票价格的钱，或者上一轮买入第二笔股票后手里剩的钱两者中较大的hold2 = Math.max(hold2, release1 - prices[i]);//在该价格点卖出第一笔股票后手里剩的钱，等于上一轮买入第一笔股票后手里剩的钱加上卖出当前股票价格的钱，或者上一轮卖出第一笔股票后手里剩的钱两者中较大的release1 = Math.max(release1, hold1 + prices[i]);//在该价格点买入第一笔股票后手里剩的钱，等于初始资金减去买入当前股票价格的钱或者初始资金（不买）中较大的hold1 = Math.max(hold1, -prices[i]);        }        return release2;    }}

Best Time to Buy and Sell Stock IV

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 at most k transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

动态规划

复杂度

时间 O(Nk) 空间 O(Nk)

思路

我们将第i天已经执行j笔交易的最大收益作为全局变量global，将第i天正好完成第j笔交易的最大收益作为局部变量local。

对于global，也就是我们要知道第i天已经执行j笔交易的最大收益，可以基于第i-1天已经执行j笔交易的最大收益和第i天正好完成第j笔交易的最大收益，即globali = max(globali-1, locali)。

对于local，也就是我们要知道第i天正好完成第j笔交易的最大收益，可以基于第i-1天正好完成第j-1笔交易的最大收益加上当天交易的差值，还有第i-1天正好完成第j笔交易的最大收益加上当天交易的差值。要注意的是，第i-1天正好完成第j-1笔交易这种情况，当前交易的差值取0和实际昨天今天差价中较大的，因为我们还有一次自由交易的余地，所以如果亏的话完全可以当天买卖避免损失。但第i-1天正好完成第j笔交易这种情况来推导第i天正好完成第j笔交易时，相当于第i天已经要连着第i-1天交易，使得第i-1天正好完成的第j笔交易和第i天正好完成的第j笔交易是同一个交易。算式是：locali = max(locali-1+max(0, diff), locali-1+diff)

注意

• 对于k > prices.length / 2的情况，我们可以用II的解法来节省空间。因为按照题意必须先买后卖，那么对于n天交易，能够产生有效收益的交易次数是小于等于n/2的，只有不同天买卖才能产生差价。对于大于n/2的那部分交易，必定是当天买卖没有任何收益的，无论交易多少次都是一样的。所以如果k > prices.length / 2，就相当于无限次交易。

• 数组的第二维初始化长度是k+1，因为我们要预留完成0笔交易的收益，是0。

代码

public class Solution {    public int maxProfit(int k, int[] prices) {        if(prices.length == 0) return 0;        //用II的解法优化k > prices.length / 2的情况        if(k > prices.length / 2){int sum = 0;for(int i = 1; i < prices.length; i++){    if(prices[i]>prices[i-1]) sum += prices[i] - prices[i-1];}return sum;        }        //初始化全局变量和局部变量        int[][] global = new int[prices.length][k+1];        int[][] local = new int[prices.length][k+1];        for(int i = 1; i < prices.length; i++){int diff = prices[i] - prices[i-1];for(int j = 1; j < k + 1; j++){    //更新局部变量    local[i][j] = Math.max(global[i-1][j-1]+Math.max(0, diff), local[i-1][j]+diff);    //更新全局变量    global[i][j] = Math.max(global[i-1][j], local[i][j]);}        }        return global[prices.length - 1][k];    }}

滚动扫描法

复杂度

时间 O(N) 空间 O(k)

思路

这个解法和III中滚动扫描法是一样的，区别在于III我们用了固定的四个变量来记录两次交易，而IV中我们需要2k个变量来记录k次交易。

注意

数组长度要初始为k+1，这样方便我们处理第一笔交易的情况。

代码

public class Solution {    public int maxProfit(int k, int[] prices) {        //用II的解法优化k > prices.length / 2的情况        if(k > prices.length / 2){int sum = 0;for(int i = 1; i < prices.length; i++){    if(prices[i]>prices[i-1]) sum += prices[i] - prices[i-1];}return sum;        }        //初始化买卖股票后剩余金钱的数组        int[] release = new int[k+1];        int[] hold = new int[k+1];        for(int i = 0; i < k+1; i++){hold[i]=Integer.MIN_VALUE;        }        for(int i = 0; i < prices.length; i++){for(int j = 1; j < k+1; j++){    //卖出第j笔交易，所剩余的钱    release[j] = Math.max(release[j], hold[j]+prices[i]);    //买入第j笔交易，所剩余的钱    hold[j] = Math.max(hold[j], release[j-1]-prices[i]);}        }        return release[k];    }}