123.Best Time to Buy and Sell Stock III---dp

题目链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/

题目大意：与122题类似，只是这里要求买卖次数只能有两次，计算两次总共的最大利润值。

法一（超时）：计算某一天之前的最大利润值与某一天之后的最大利润值，然后用for循环遍历得到最大值，时间复杂度是o(n^2)，代码如下：

 1 int res = 0;
 2         for(int i = 0; i < prices.length; i++) {
 3             int maxPre = 0;
 4             int min = Integer.MAX_VALUE;
 5             //0 to i-1
 6             for(int j = 0; j < i; j++) {
 7                 if(prices[j] < min) {
 8                     min = prices[j];
 9                 }
10                 else if(prices[j] - min > maxPre){
11                     maxPre = prices[j] - min;
12                 }
13             }
14             //i to n-1
15             int maxPost = 0;
16             min = Integer.MAX_VALUE;
17             for(int j = i; j < prices.length; j++) {
18                 if(prices[j] < min) {
19                     min = prices[j];
20                 }
21                 else if(prices[j] - min > maxPost){
22                     maxPost = prices[j] - min;
23                 }
24             }
25             
26             if(maxPre + maxPost > res) {
27                 res = maxPre + maxPost;
28             }
29         }
30         return res;

View Code

法二（借鉴）：动态规划，利用法一的思路，只是这里不用for循环嵌套遍历得到最大值，而是用两个数组分别记录某一天之前的最大利润值和某一天之后的最大利润值，然后再另开一个for循环，计算比较得到最大值。这里有两个动规公式：

1.数组记录最大利润：

　　1）某一天之前：preProfit[i] = max(preProfit[i - 1], prices[i] - min);

　　2）某一天之后：postProfit[i] = max(postProfit[i + 1], max - prices[i]);

2.for循环计算得到最大值：res = max(res, preProfit[i] + postProfit[i]);

代码如下（耗时1ms）：

 1         int length = prices.length;
 2         int[] preProfit = new int[length];
 3         int[] postProfit = new int[length];
 4         //从前往后找，0 to i，用数组记录每一天i之前所能获得的最大利润，计算过程与121题类似
 5         int minPrice = Integer.MAX_VALUE;
 6         int max = 0;
 7         for(int i = 0; i < length; i++) {
 8             if(prices[i] < minPrice) {
 9                 minPrice = prices[i];
10             }
11             else if(prices[i] - minPrice > max) {
12                 max = prices[i] - minPrice;
13             }
14             preProfit[i] = max;
15         }
16         //从后往前，i to n-1，用数组记录每一天i之后所能获得的最大利润
17         //注意：从后往前找的时候，应该记录当前位置之后的最大价值，然后将当前位置的价值与最大价值进行比较
18         int maxPrice = Integer.MIN_VALUE;
19         max = 0;
20         for(int i = length - 1; i >= 0; i--) {
21             if(prices[i] > maxPrice) {
22                 maxPrice = prices[i];
23             }
24             else if(maxPrice - prices[i] > max) {
25                 max = maxPrice - prices[i];
26             }
27             postProfit[i] = max;
28         }
29         
30         int res = 0;
31         for(int i = 0; i < length; i++) {
32             if(preProfit[i] + postProfit[i] > res) {
33                 res = preProfit[i] + postProfit[i];
34             }
35         }
36         return res;

View Code

法三（借鉴）：参考：http://blog.csdn.net/u012501459/article/details/46514309解法二。

123.Best Time to Buy and Sell Stock III---dp

推荐阅读