@natsumi 2016-09-30T08:53:39.000000Z 字数 8069 阅读 1533

# Best Time to Buy and Sell Stock

Algorithms

## 1. Best Time to Buy and Sell Stock I

LeetCode121
Description: 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.

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

## 2. Best Time to Buy and Sell Stock II

LeetCode122
Description: 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).

    public int maxProfit(int[] prices) {//1ms        if (prices.length < 2) {            return 0;        }        int tmp = prices[0];        int maxProfit = 0;        for (int i = 1; i < prices.length; i++) {            if (prices[i] > tmp) {                maxProfit += prices[i] - tmp;            }            tmp = prices[i];        }        return maxProfit;    }

LeetCode中editorial solution
Approach #2 (Peak Valley Approach) [Accepted]

    public int maxProfit2(int[] prices) {        int i = 0;        int valley = prices[0];        int peak = prices[0];        int maxprofit = 0;        while (i < prices.length - 1) {            while (i < prices.length - 1 && prices[i] >= prices[i + 1])                i++;            valley = prices[i];            while (i < prices.length - 1 && prices[i] <= prices[i + 1])                i++;            peak = prices[i];            maxprofit += peak - valley;        }        return maxprofit;    }

## 3. Best Time to Buy and Sell Stock III

LeetCode123
Description: 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).

### 3.1 方法一

public class Solution {    public int maxProfit(int[] prices) {        if (prices.length < 2) return 0;        int n = prices.length;        int[] preProfit = new int[n];        int[] postProfit = new int[n];        int curMin = prices[0];        for (int i = 1; i < n; i++) {            curMin = Math.min(curMin, prices[i]);            preProfit[i] = Math.max(preProfit[i - 1], prices[i] - curMin);        }        int curMax = prices[n - 1];        for (int i = n - 2; i >= 0; i--) {            curMax = Math.max(curMax, prices[i]);            postProfit[i] = Math.max(postProfit[i + 1], curMax - prices[i]);        }        int maxProfit = 0;        for (int i = 0; i < n; i++) {            maxProfit = Math.max(maxProfit, preProfit[i] + postProfit[i]);        }        return  maxProfit;    }}

### 3.2 方法二

    public int maxProfit(int[] prices) {        // these four variables represent your profit after executing corresponding transaction        // in the beginning, your profit is 0.        // when you buy a stock ,the profit will be deducted of the price of stock.        int firstBuy = Integer.MIN_VALUE, firstSell = 0;        int secondBuy = Integer.MIN_VALUE, secondSell = 0;        for (int curPrice : prices) {            if (firstBuy < -curPrice) firstBuy = -curPrice; // the max profit after you buy first stock            if (firstSell < firstBuy + curPrice) firstSell = firstBuy + curPrice; // the max profit after you sell it            if (secondBuy < firstSell - curPrice) secondBuy = firstSell - curPrice; // the max profit after you buy the second stock            if (secondSell < secondBuy + curPrice) secondSell = secondBuy + curPrice; // the max profit after you sell the second stock        }        return secondSell; // secondSell will be the max profit after passing the prices    }

## 4 Best Time to Buy and Sell Stock IV

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

### 4.1 方法一

profit[i][j] = max(profit[i – 1][j], profit[i – 1][j – 1] + diff)

local[i][j] = max(global[i – 1][j – 1] , local[i – 1][j] + diff)
global[i][j] = max(global[i – 1][j], local[i][j])

local[i][j]和global[i][j]的区别是：local[i][j]意味着在第i天一定有交易（卖出）发生，当第i天的价格高于第i-1天（即diff > 0）时，那么可以把这次交易（第i-1天买入第i天卖出）跟第i-1天的交易（卖出）合并为一次交易，即local[i][j]=local[i-1][j]+diff；当第i天的价格不高于第i-1天（即diff<=0）时，那么local[i][j]=global[i-1][j-1]+diff，而由于diff<=0，所以可写成local[i][j]=global[i-1][j-1]。global[i][j]就是我们所求的前i天最多进行k次交易的最大收益，可分为两种情况：如果第i天没有交易（卖出），那么global[i][j]=global[i-1][j]；如果第i天有交易（卖出），那么global[i][j]=local[i][j]。

    public static int maxProfit(int k, int[] prices) {//8ms        if (prices.length < 2) return 0;        int days = prices.length;        if (k >= days) return maxProfitII(prices);        int[][] local = new int[days][k + 1];        int[][] global = new int[days][k + 1];        for (int i = 1; i < days; i++) {            int diff = prices[i] - prices[i - 1];            for (int j = 1; j <= k; j++) {                local[i][j] = Math.max(global[i - 1][j - 1], local[i - 1][j] + diff);                global[i][j] = Math.max(global[i - 1][j], local[i][j]);                System.out.print("local&global(" + i + "," + j + "): " + local[i][j] + " " + global[i][j] + "\t");            }            System.out.println();        }        return global[days - 1][k];    }    public static int maxProfitII(int[] prices) {        int maxProfit = 0;        for (int i = 1; i < prices.length; i++) {            if (prices[i] > prices[i - 1]) {                maxProfit += prices[i] - prices[i - 1];            }        }        return maxProfit;    }

dicuss中有另一个算法beat 99+%

### 4.2 方法二

    public static int maxProfit2(int k, int[] prices) {//2ms        if (k <= 0 || prices == null || prices.length <= 0) return 0;        if (k > prices.length / 2) { // in this case, it's the same problem as Best Time to Buy & Sell Stock II            int max = 0;            for (int i = 0; i < prices.length - 1; i++) {                int diff = prices[i + 1] - prices[i];                max += diff > 0 ? diff : 0;            }            return max;        } else {            int[] buy = new int[k];//buy[j]用来表示第j次买入后的手中的余额            int[] sell = new int[k];//sell[j]用来表示第j次卖出后的手中的余额            Arrays.fill(buy, Integer.MIN_VALUE);            int buffer = 0;// used to avoid duplicate calculation            int tmp = 0;            for (int i = 0; i < prices.length; i++) {                tmp = 0;                for (int j = 0; j < k; j++) {                    buffer = tmp - prices[i];//此时tmp是第j次买入前（即第j-1次卖出后）的余额                    if (buy[j] < buffer)//若第i天进行买入后余额 > i-1天内完成第j次买入后的余额                        buy[j] = buffer;//则买入，修改buy[j]                    buffer = buy[j] + prices[i];//计算若以第i天的价格进行第j次卖出后的余额                    if (sell[j] < buffer)//若第i天进行第j次卖出后的余额 > i-1天进行j次交易后的余额                        sell[j] = buffer;//则卖出，修改sell[j]                    tmp = sell[j];                    System.out.print("buy&sell(" + i + "," + j + "): " + buy[j] + " " + sell[j] + "\t");                }                System.out.println();            }            return sell[k - 1];        }    }

    public static void main(String[] args) {        int[] p = {7, 2, 5, 6, 6, 4, 2, 8};        System.out.println(maxProfit(3, p));        System.out.println(maxProfit2(3, p));    }
//括号里是i和jlocal&global(1,1): 0 0  local&global(1,2): 0 0  local&global(1,3): 0 0  local&global(2,1): 3 3  local&global(2,2): 3 3  local&global(2,3): 3 3  local&global(3,1): 4 4  local&global(3,2): 4 4  local&global(3,3): 4 4  local&global(4,1): 4 4  local&global(4,2): 4 4  local&global(4,3): 4 4  local&global(5,1): 2 4  local&global(5,2): 4 4  local&global(5,3): 4 4  local&global(6,1): 0 4  local&global(6,2): 4 4  local&global(6,3): 4 4  local&global(7,1): 6 6  local&global(7,2): 10 10    local&global(7,3): 10 1010buy&sell(0,0): -7 0 buy&sell(0,1): -7 0 buy&sell(0,2): -7 0 buy&sell(1,0): -2 0 buy&sell(1,1): -2 0 buy&sell(1,2): -2 0 buy&sell(2,0): -2 3 buy&sell(2,1): -2 3 buy&sell(2,2): -2 3 buy&sell(3,0): -2 4 buy&sell(3,1): -2 4 buy&sell(3,2): -2 4 buy&sell(4,0): -2 4 buy&sell(4,1): -2 4 buy&sell(4,2): -2 4 buy&sell(5,0): -2 4 buy&sell(5,1): 0 4  buy&sell(5,2): 0 4  buy&sell(6,0): -2 4 buy&sell(6,1): 2 4  buy&sell(6,2): 2 4  buy&sell(7,0): -2 6 buy&sell(7,1): 2 10 buy&sell(7,2): 2 10 10

• 私有
• 公开
• 删除