Description:
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.
Example
Given an example [4,4,6,1,1,4,2,5], return 6.
Note
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Solution:
class Solution {
public:
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
auto sz = (int)prices.size();
if (sz == 0) return 0;
vector<int> vec1(sz, 0);
vector<int> vec2(sz, 0);
int m1 = prices[0];
int m2 = prices[sz-1];
for (int i = 1; i < sz; ++i) {
m1 = min(m1, prices[i]);
vec1[i] = max(prices[i]-m1, vec1[i-1]);
m2 = max(m2, prices[sz-1-i]);
vec2[sz-1-i] = max(m2-prices[sz-1-i], vec2[sz-i]);
}
int rc = 0;
for (int i = 0; i < sz; ++i) {
rc = max(rc, vec1[i]+vec2[i]);
}
return rc;
}
};
转载于:https://www.cnblogs.com/deofly/p/best-time-to-buy-and-sell-stock-iii.html
相关资源：JAVA上百实例源码以及开源项目
