首页 > 代码库 > LeetCode123:Best Time to Buy and Sell Stock III
LeetCode123:Best Time to Buy and Sell Stock III
题目:
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).
解题思路:
话说这题同前两题难度瞬间就拉开好多,哎,编程能力还是不行啊,如果不是谷歌各路大神解题报告http://blog.csdn.net/pickless/article/details/12034365,真心想不出来。
这题实际上用到了DP和分段的思想。
首先,根据题意,要求至少买卖两次(就因为有这限制,使得题目难度突然就增加了),所以,我们可以进行分段。
寻找一个点i,将原来的price[0..n-1]分割为price[0..i]和price[i..n-1],分别求两段的最大profit,可知分段就是使得买卖至少进行两次。
下面求price[0..i]和price[i..n-1]两段的最大profit时,利用了DP思想。
对于点i+1,求price[0..i+1]的最大profit时,很多工作是重复的,在求price[0..i]的最大profit中已经做过了。
类似于Best Time to Buy and Sell Stock,可以在O(1)的时间从price[0..i]推出price[0..i+1]的最大profit。
但是如何从price[i..n-1]推出price[i+1..n-1]?反过来思考,我们可以用O(1)的时间由price[i+1..n-1]推出price[i..n-1]。
最终算法:
数组l[i]记录了price[0..i]的最大profit,
数组r[i]记录了price[i..n]的最大profit。
已知l[i],求l[i+1]是简单的,同样已知r[i],求r[i-1]也很容易。
最后,我们再用O(n)的时间找出最大的l[i]+r[i],即为题目所求。
实现代码:
#include <iostream> #include <vector> using namespace std; /** 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). */ class Solution { public: int maxProfit(vector<int> &prices) { if(prices.empty()) return 0; int n = prices.size(); int *l = new int[n]; int *r = new int[n]; l[0] = 0; int lmin = prices[0]; for(int i = 1; i < n; i++) { lmin = min(prices[i],lmin); l[i] = max(l[i-1], prices[i] - lmin); } r[n-1] = 0; int rmax = prices[n-1]; for(int i = n - 2; i >= 0; i--) { rmax = max(rmax, prices[i]); r[i] = max(r[i+1], rmax - prices[i]); } int maxprofit = 0; for(int i = 0; i < n; i++) { maxprofit = max(maxprofit, l[i] + r[i]); } delete l; delete r; return maxprofit; } }; int main(void) { int arr[] = {2,4,5,1,7,10}; int n = sizeof(arr) / sizeof(arr[0]); vector<int> stock(arr, arr+n); Solution solution; int max = solution.maxProfit(stock); cout<<max<<endl; return 0; }