详细见：leetcode.com/problems/best-time-to-buy-and-sell-stock-iii
Java Solution: github
package leetcode; import java.util.ArrayList; /* * 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). */ public class P123_BestTimetoBuyandSellStockIII { public static void main(String[] args) { Solution3 s = new Solution3(); System.out.println(s.maxProfit(new int[] {})); System.out.println(s.maxProfit(new int[] {7, 1, 5, 3, 6, 4})); System.out.println(s.maxProfit(new int[] {9, 1, 2, 3, 4, 2, 3, 4, 3, 4})); System.out.println(s.maxProfit(new int[] {1, 2, 0, 3})); System.out.println(s.maxProfit(new int[] {1, 2, 3, 2, 7, 0, 100})); System.out.println(s.maxProfit(new int[] {1, 2, 3, 2, 7, 0, 4, 3, 100})); System.out.println(s.maxProfit(new int[] {9, 8, 7, 6})); System.out.println(s.maxProfit(new int[] {1, 2})); System.out.println(s.maxProfit(new int[] {1,9,2,8,3,7,4,6,5})); } /* * 一次WA * AC * O(N ^ 3) * 56 ms */ static class Solution { public int maxProfit(int[] prices) { int ans = 0; ArrayList<Integer> add = new ArrayList<Integer>(); ArrayList<Integer> pre = new ArrayList<Integer>(); int index = - 1; for (int i = 0; i < prices.length; i ++) { if (index == -1) { add.add(i); pre.add(0); index ++; continue; } if (prices[i] > prices[add.get(index)]) { add.set(index, i); } else if (prices[i] < prices[add.get(index)]) { if (i == pre.get(index) + 1) { add.remove(index); pre.remove(index); add.add(i); pre.add(i); } else { add.add(i); pre.add(i); index ++; } } } if (index == - 1) { return 0; } if (prices.length == pre.get(index) + 1) { add.remove(index); pre.remove(index); } int i_pre_min = Integer.MAX_VALUE; for (int i = 0; i < add.size(); i ++) { i_pre_min = Math.min(i_pre_min, prices[pre.get(i)]); int i_val = prices[add.get(i)] - i_pre_min; ans = Math.max(ans, i_val); for (int j = i + 1; j < add.size(); j ++) { if (add.get(i) >= pre.get(j)) { continue; } int j_pre_min = prices[pre.get(j)]; for (int k = i + 1; k < j; k ++) { j_pre_min = Math.min(j_pre_min, prices[pre.get(k)]); } ans = Math.max(ans, i_val + prices[add.get(j)] - j_pre_min); } } return ans; } } /* * 7 ms * 9.48% */ static class Solution2 { public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int ans = 0; int[] forward = new int[prices.length]; int forward_min = Integer.MAX_VALUE; for (int i = 0; i < prices.length; i ++) { forward_min = Math.min(forward_min, prices[i]); if (i != 0) { forward[i] = Math.max(prices[i] - forward_min, forward[i - 1]); } } int[] backward = new int[prices.length]; int backward_max = Integer.MIN_VALUE; for (int i = prices.length - 1; i > - 1; i --) { backward_max = Math.max(backward_max, prices[i]); if (i != prices.length - 1) { backward[i] = Math.max(backward_max - prices[i], backward[i + 1]); } } for (int i = 0; i < prices.length; i ++) { ans = Math.max(ans, forward[i] + backward[i]); } return ans; } } /* * 可以更快的 * 7 ms * 9.48% */ static class Solution3 { public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int ans = 0; int[] forward = new int[prices.length]; int forward_min = Integer.MAX_VALUE; for (int i = 0; i < prices.length; i ++) { forward_min = Math.min(forward_min, prices[i]); if (i != 0) { forward[i] = Math.max(prices[i] - forward_min, forward[i - 1]); } } int backward = 0; int backward_max = Integer.MIN_VALUE; for (int i = prices.length - 1; i > - 1; i --) { backward_max = Math.max(backward_max, prices[i]); if (i != prices.length - 1) { backward = Math.max(backward_max - prices[i], backward); } ans = Math.max(ans, forward[i] + backward); } return ans; } } }C Solution: github
/* url: leetcode.com/problems/best-time-to-buy-and-sell-stock-iii on_n: AC 3ms 43.33% on_n_2: AC 3ms 43.33% */ #include <stdio.h> #include <stdlib.h> #include <limits.h> void swap(int* a, int *b) { int t = *a; *a = *b; *b = t; } void heap_up(int* h, int j) { int p = (j-1) / 2, c = j; while (p != c) { if (h[p] > h[c]) { swap(h+p, h+c); c = p; p = (c-1) / 2; } else break; } } void heap_dn(int* h, int hn, int i) { int p = 0, c = 1; while (c < hn) { if (c+1 < hn && h[c+1] < h[c]) c ++; if (h[p] > h[c]) { swap(h+p, h+c); p = c; c = 2*p + 1; } else break; } } void heap_add(int* h, int *hi, int hn, int v) { if ((*hi) != hn) { h[*hi] = v; heap_up(h, *hi); (*hi) ++; } else { if (v > h[0]) { h[0] = v; heap_dn(h, hn, 0); } } } int _max(int a, int b) { return a < b ? b : a; } int _min(int a, int b) { return a < b ? a : b; } //TLE int onn_nn(int* p, int pn) { int** m = NULL, i = 0, j = 0; int iv = 0, jv = 0, ans = 0; if (pn < 2) return 0; m = (int**) malloc(sizeof(int*) * pn); for (i = 0; i < pn; i ++) m[i] = (int*) malloc(sizeof(int) * pn); for (i = 0; i < pn ; i ++) m[i][i] = 0; for (i = 0; i < pn; i ++) { iv = p[i]; for (j = i+1; j < pn; j ++) { jv = p[j]; if (jv - iv > m[i][j-1]) m[i][j] = jv - iv; else m[i][j] = m[i][j-1]; } } for (i = 0; i < pn; i ++) { for (j = i+2; j < pn; j ++) { ans = _max(ans, m[i][j-1]+m[j][pn-1]); } ans = _max(ans, m[i][pn-1]); } return ans; } int on_n(int* p, int pn) { int* l = (int*) malloc(sizeof(int) * (pn+1)); int* r = (int*) malloc(sizeof(int) * (pn+1)); int i = 0, mv = INT_MAX, m = 0, ans = 0; l[0] = 0; for (i = 1; i <= pn; i ++) { mv = _min(p[i-1], mv); m = _max(m, p[i-1]-mv); l[i] = m; } mv = INT_MIN; m = 0; r[pn] = 0; for (i = pn-1; i > -1; i --) { mv = _max(p[i], mv); m = _max(m, mv-p[i]); r[i] = m; } for (i = 0; i <= pn; i ++) { ans = _max(ans, l[i]+r[i]); } free(l); free(r); return ans; } int on_n_2(int* p, int pn) { int* l = (int*) malloc(sizeof(int) * (pn+1)); int i = 0, mv = INT_MAX, m = 0, ans = 0; l[0] = 0; for (i = 1; i <= pn; i ++) { mv = _min(p[i-1], mv); m = _max(m, p[i-1]-mv); l[i] = m; } mv = INT_MIN; m = 0; for (i = pn-1; i > -1; i --) { mv = _max(p[i], mv); m = _max(m, mv-p[i]); ans = _max(ans, l[i]+m); } ans = _max(ans, l[pn] + 0); free(l); return ans; } int maxProfit(int* p, int pn) { return on_n_2(p, pn); } int main() { int p[] = {1, 7, 2, 9, 3, 11, 4, 13, 5, 15}; int pn = 10; printf("answer is %d\n", maxProfit(p, pn)); return 0; }Python Solution: github
#coding=utf-8 ''' url: leetcode.com/problems/best-time-to-buy-and-sell-stock-iii @author: zxwtry @email: zxwtry@qq.com @date: 2017年5月5日 @details: Solution: 86ms 36.12% ''' class Solution(object): def maxProfit(self, p): """ :type p: List[int] :rtype: int """ l, r = [], [0]*(len(p)+1) mv, m = 1 << 31, 0 l.append(0) for v in p: mv = min(mv, v) m = max(m, v-mv) l.append(m) mv, m = 0, 0 for i in range(len(p)-1, -1, -1): mv = max(p[i], mv) m = max(m, mv-p[i]) r[i] = m return max(l[i]+r[i] for i in range(len(p)+1)) if __name__ == "__main__": p = [2,1,2,0,1] print(Solution().maxProfit(p))
