leetcode解题: best time to buy and sell stock III (123)

发表于 | 分类于

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

解法1： Divide & Conquer O(N^2) Time + O(N) Space

思路是利用I的解题方法，对于一个(i,j)范围的数组，可以用O(N)的时间和O(1)的空间算出最大的利润
那么可以将原数组分割为(0,i) + (i,length - 1)的两个数组，分别计算每个范围内的最大利润再相加。
一共有N种分割方法，所以总的时间复杂度是O(N^2)
这个解法lintcode可以AC,leetcode会TLE，所以需要改进这个解法，最好的是O(N) Time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int maxProfit(int[] prices) {
	if (prices == null || prices.length == 0) {
		return 0;
	}
	int res = 0;
	for (int i = 0; i < prices.length - 1; i++) {
		int left = maxSingleTransition(prices, 0, i);
		int right = maxSingleTransition(prices, i, prices.length - 1);
		int sum = left + right;
		res = Math.max(res, sum);
	}
	return res;
}
private int maxSingleTransition(int[] prices, int start, int end) {
	int min = prices[start];
	int res = 0;
	for (int i = start; i <= end; i++) {
		res = Math.max(res, prices[i] - min);
		min = Math.min(min, prices[i]);
	}
	return res;
}

解法2：两次DP，O(N) Time + O(N) Space

思路还是类似于第一种解法，但是做了优化。计算(0,i)的时候实际可以运用(0,i-1)的结果。同样，计算(i,length - 1)的时候可以
运用(i+1,length - 1)的结果。这就引出了用两个dp数组先记录下每一个区间的最大收益，然后再扫描一遍得到左右两个区间和的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int maxProfit(int[] prices) {
	if (prices == null || prices.length == 0) {
		return 0;
	}
	int[] left = new int[prices.length];
	int[] right = new int[prices.length];
	// Scan from left
	int min = prices[0];
	for (int i = 1; i < prices.length; i++) {
		left[i] = Math.max(left[i - 1], prices[i] - min);
		min = Math.min(min, prices[i]);
	}
	// Scan from right
	int max = prices[prices.length - 1];
	for (int i = prices.length - 2; i >= 0; i--) {
		right[i] = Math.max(right[i + 1], max - prices[i]);
		max = Math.max(max, prices[i]);
	}
	// search for the largest sum
	int res = 0;
	for (int i = 0; i < prices.length; i++) {
		res = Math.max(res, left[i] + right[i]);
	}
	return res;
}

解法３: 用交替的dp方程组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int t_i10 = 0, t_i11 = Integer.MIN_VALUE, t_i20 = 0, t_i21 = Integer.MIN_VALUE;
        for (int price : prices) {
            t_i20 = Math.max(t_i20, t_i21 + price);
            t_i21 = Math.max(t_i21, t_i10 - price);
            t_i10 = Math.max(t_i10, t_i11 + price);
            t_i11 = Math.max(t_i11, -price);
        }
        return t_i20;
    }
}