leetcode的题目：
leetcode的题目都很简练，但是很有趣，认真地做吧。
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).
a. 对于输入为n，最多可以买卖两次，求最大的盈利。
b. 买两次的收益通常比买一次来的大。
c. 对于输入规模为n，当n>=4时可以将n分为两部分，且分类的方法有n-3种。每份的最少个数为2。因为n个元素，总共有n-1条缝隙可以划分，又最左或最右至少要有两个元素，所以n-1-2 = n-3 种。
d. 求得划分一次（买卖两次）的每种划分的最大盈利，和不划分的最大盈利，即得到最大的盈利。
max_profit = max{买卖两次（划分一次），买卖一次（不进行划分）}
e. 定义状态矩阵dp_be[i], 表示以0为起点，i为终点的子串的最大盈利。
dp_be[0] = 0; int i, max_profit = 0, cur_min = prices[0]; for(i = 1; i < len; i++) { max_profit = max(max_profit, prices[i]-cur_min); cur_min = min(cur_min, prices[i]); dp_be[i] = max_profit; // 在i时卖出的最大收益 } f. 定义状态矩阵dp_af[i],表示以i为起点，n-1(最后元素)为终点的子串的最大盈利
max_profit = 0; int cur_max = prices[len-1]; for(i = len-2; i >= 0; i--) { max_profit = max(max_profit, cur_max-prices[i]); cur_max = max(cur_max, prices[i]); dp_af[i] = max_profit; } g. 由此可得，对于以i为划分点，将n个元素分成两个子串，要求两个子串之和最大，根据贪心算法思想，要求每个子串都去的最大值。对i从1到n-3循环得到最大值。
// 放入只买一次的最大值 int max = dp_be[len-1]; // 在同一天卖了再买是没有意义的 // 求两个数组和的最大值 for(i = 1; i < len-1; i++) { if(dp_be[i]+dp_af[i+1] > max) max = dp_be[i]+dp_af[i+1]; } 主要：dp_be[i]表示0开始，i结束的子串的最大盈利，所以它对应的尾部子串为dp_af[i+1]，表示以i+1开始，n-1为终点的子串的最大盈利。
h. 代码
int Solution::maxProfit2(vector &prices) { int len = prices.size(); if(len < 2) return 0; int *dp_be = new int[len]; // 记录前向最大 int *dp_af = new int[len]; // 记录后向最大 dp_be[0] = 0; int i, max_profit = 0, cur_min = prices[0]; for(i = 1; i < len; i++) { max_profit = max(max_profit, prices[i]-cur_min); cur_min = min(cur_min, prices[i]); dp_be[i] = max_profit; // 在i时卖出的最大收益 } dp_af[len-1] = 0; max_profit = 0; int cur_max = prices[len-1]; for(i = len-3; i >= 0; i--) { max_profit = max(max_profit, cur_max-prices[i]); cur_max = max(cur_max, prices[i]); dp_af[i] = max_profit; } if(len == 2) return dp_be[len-1]; else { // 放入只买一次的最大值 int max = dp_be[len-1]; // 在同一天卖了再买是没有意义的 // 求两个数组和的最大值 for(i = 1; i < len-1; i++) { if(dp_be[i]+dp_af[i+1] > max) max = dp_be[i]+dp_af[i+1]; } return max; }}
i. 画个图说明以下
