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 (i.e., you must sell the stock before you buy again).
Example 1:
题目
和之前一样，这次你至多能买卖两次。
思路
1. Split the array into two parts, one trade each.
2. Say that f(i) stands for max profit in [0,i] , g(i) stands for max profix in [i, n-1] , then update and finally return max(f(i) + g(i))
代码
1 // Best Time to Buy and Sell Stock III 2 // 时间复杂度O(n)，空间复杂度O(n) 3 public class Solution { 4 public int maxProfit(int[] prices) { 5 if (prices.length < 2) return 0; 6 7 final int n = prices.length; 8 int[] f = new int[n]; 9 int[] g = new int[n]; 10 11 for (int i = 1, valley = prices[0]; i < n; ++i) { 12 valley = Math.min(valley, prices[i]); 13 f[i] = Math.max(f[i - 1], prices[i] - valley); 14 } 15 16 for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) { 17 peak = Math.max(peak, prices[i]); 18 g[i] = Math.max(g[i], peak - prices[i]); 19 } 20 21 int max_profit = 0; 22 for (int i = 0; i < n; ++i) 23 max_profit = Math.max(max_profit, f[i] + g[i]); 24 25 return max_profit; 26 } 27 }
转载于:https://www.cnblogs.com/liuliu5151/p/10042110.html
相关资源：数据结构—成绩单生成器