题目
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).
方法
仅仅能进行两次买入卖出，非常自然的想法就是进行二分。
设数组的长度是len， A[0,..,i] ,A[i,...len - 1] 分别计算数组两部分的maxProfit，然后求和。
上述操作须要进行n次，然后返回最大的结果。显然时间复杂度(N^2)。
能够考虑使用空间换时间，从前往后遍历一遍数组，能够获取从0到i的最大maxProfit，将结果放入到数组中，
从后往前遍历一遍数组，能够获取从i到len-1的最大maxProfit，将结果放入到数组中，
遍历一遍，就能够获得结果。
public int maxProfit(int[] prices) { if (prices == null) { return 0; } int len = prices.length; if (len == 0 || len == 1) { return 0; } int[] maxPre = new int[len]; int[] maxPost = new int[len]; int min = prices[0]; int max = prices[0]; int maxPro = 0; maxPre[0] = 0; for (int i = 1; i < len; i++) { if (prices[i] > max) { max = prices[i]; int tempMaxPro = max - min; if (tempMaxPro > maxPro) { maxPro = tempMaxPro; } } else if (prices[i] < min) { min = prices[i]; max = prices[i]; } maxPre[i] = maxPro; } min = prices[len - 1]; max = prices[len - 1]; maxPro = 0; maxPost[len - 1] = 0; for (int i = len - 1; i > 0; i--) { if (prices[i - 1] > max) { min = prices[i - 1]; max = prices[i - 1]; } else if (prices[i -1] < min) { min = prices[i - 1]; int tempMaxPro = max - min; if (tempMaxPro > maxPro) { maxPro = tempMaxPro; } } maxPost[i - 1] = maxPro; } maxPro = 0; for (int i = 0; i < len; i++) { int tempMaxPro = maxPre[i] + maxPost[i]; if (maxPro < tempMaxPro ) { maxPro = tempMaxPro; } } return maxPro; }
转载于:https://www.cnblogs.com/bhlsheji/p/4004904.html
相关资源：数据结构—成绩单生成器