Noob
0%

Best Time to Buy and Sell Stocks

发表于 更新于 分类于 ，

Best Time to Buy and Sell stock (Simple DP)

Giving an array of values, say the ith value is the price of stock of the ith day. If you can perform at most one transaction (ie. Buy one and sell one share of stock), find the maximum profit.

Keep tracing the minimum price before the ith day and calculating the maximum profit during scanning.

1
2
3
4
5
6
7
8
9
public int maxProfit(int[] prices) {
    if(prices == null || prices.length <= 1) return 0;
    int result = 0, min = prices[0];
    for(int i = 1; i < prices.length; ++i) {
        result = Math.max(result, prices[i] - min);
        min = Math.min(min, prices[i]);
    }
    return result;
}

Best Time to Buy and Sell stock(Greed)

Giving an array of values, say the ith value is the price of stock of the ith day. If you can perform as many transactions (ie. Buy one and sell one share of stock) as you like, find the maximum profit.

Using greed algorithm, perform the transaction only if there is profit to make between two continuous days.

1
2
3
4
5
6
7
8
9
public int maxProfit(int[] prices) {
    if(prices == null || prices.length <= 1) return 0;
    int result = 0;
    for(int i = 1; i < prices.length; ++i) {
        if(prices[i] > prices[i - 1])
            result += prices[i] - prices[i - 1];
    }
    return result;
}

Best Time to Buy and Sell stock(Devide and Conquer & DP)

Giving an array of values, say the ith value is the price of stock of the ith day. If you can perform at most two transactions (ie. Buy one and sell one share of stock), find the maximum profit.

This can be solved by “Devide and Conquer”, using left array to track maximum profit by one transaction before the ith day, and right array to track maximum profit by one transaction after the ith day.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int maxProfit(int[] prices) {
    if(prices == null || prices.length <= 1) return 0;
    int m = prices.length;
    int[] left = new int[m];
    int[] right = new int[m];
    int minP = prices[0];
    for(int i = 1; i < m; ++i) {
        left[i] = Math.max(left[i - 1], prices[i] - minP);
        minP = Math.min(minP, prices[i]);
    }
    int maxP = prices[m - 1];
    for(int i = m - 2; i >= 0; --i) {
        right[i] = Math.max(right[i + 1], maxP - prices[i]);
        maxP = Math.max(maxP, prices[i]);
    }
    int result = 0;
    for(int i = 0; i < m; ++i)
        result = Math.max(result, left[i] + right[i]);
    return result;
}

Best Time to Buy and Sell stock(2D DP)

Giving an array of values, say the ith value is the price of stock of the ith day. If you can perform at most k transactions (ie. Buy one and sell one share of stock), find the maximum profit.

Using 2D dynamic programming, dp[i][j] means maximum profit until ith transaction and jth day.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int maxProfit(int k, int[] prices) {
    if(prices == null || prices.length <= 1) return 0;
    int m = prices.length;
    if(k >= m / 2) {
        int result = 0;
        for(int i = 1; i < prices.length; ++i) {
            if(prices[i] > prices[i - 1])
                result += prices[i] - prices[i - 1];
        }
        return result;
    }
    int[][] dp = new int[k + 1][m];
    for(int i = 1; i <= k; ++i) {
        int t = -prices[0];
        for(int j = 1; j < m; ++j) {
            dp[i][j] = Math.max(dp[i][j - 1], t + prices[j]);
            t = Math.max(t, dp[i - 1][j - 1] - prices[j]);
        }
    }
    return dp[k][m - 1];
}

Reference

https://leetcode.com/discuss/25603/a-concise-dp-solution-in-java