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).
思路：
方案一：两次交易，得到最大收入。 设原本有length个数据，用n把数据分为[0 ~ n-1] 和 [n ~ length-1]两个部分，分别求最大收入，再加起来。结果超时了。
方案二：设数据是 0 2 1 4 2 4 7
求后一个数字和前一个数字的差值： 2 -1 3 -2 2 3
把连续符合相同的数累加 2 -1 3 -2 5
这样处理后，假设有m个数据， 用n把数据分为[0 ~ n-1] 和 [n ~ m-1]两个部分, 分别求两个部分的最大连续子段和。
由于经过预处理，数据变少了很多，所以就AC了。
int maxProfit3(vector<int> &prices) {
if(prices.size() < )
{
return ;
}
//第一步：把prices中的数 两两间的差值算出来 把差值符号相同的加在一起
vector<int> dealPrices;
vector<int>::iterator it;
int last = prices[];
int current;
int sumNum = ;
for(it = prices.begin() + ; it < prices.end(); it++)
{
current = *it;
if((current - last >= && sumNum >= ) || (current - last <= && sumNum <= ))
{
sumNum += current - last;
}
else
{
dealPrices.push_back(sumNum);
sumNum = current - last;
}
last = current;
}
if(sumNum != )
{
dealPrices.push_back(sumNum);
}
//第二步
if(dealPrices.size() == )
{
return dealPrices[] > ? dealPrices[] : ;
}
else
{
int maxprofit = ;
for(int n = ; n < dealPrices.size(); n++)
{
//求前半段最大连续子段和
int maxSum1 = ;
int maxSum2 = ;
int curSum = ;
for(int i = ; i < n; i++)
{
curSum = (curSum > ) ? curSum + dealPrices[i] : dealPrices[i];
maxSum1 = (curSum > maxSum1) ? curSum : maxSum1;
}
//求后半段最大连续子段和
curSum = ;
for(int i = n; i < dealPrices.size(); i++)
{
curSum = (curSum > ) ? curSum + dealPrices[i] : dealPrices[i];
maxSum2 = (curSum > maxSum2) ? curSum : maxSum2;
}
if(maxSum1 + maxSum2 > maxprofit)
{
maxprofit = maxSum1 + maxSum2;
}
}
return maxprofit;
}
虽然我的AC了，但实际上还是个O(N^2)的算法，来看看大神们的O(N)代码。
第一种：https://oj.leetcode.com/discuss/14806/solution-sharing-commented-code-o-n-time-and-o-n-space
用两个数组left[],right[].
left记录当前值减去它前面的最小值的结果
right记录 当前值后面的最大值减去当前值的结果
把 left[i]+right[i+1] 针对所有的i遍历一遍 得到最大的值就是答案
public class Solution {
public int maxProfit(int[] prices) {
if (prices.length < ) return ;//one of zero days, cannot sell
// break the problem in to subproblems, what is the max profit if i decide to buy and sell one stock on or before day i
// and the other stock after day i
int[] left = new int[prices.length];//store the max profit so far for day [0,i] for i from 0 to n
int[] right = new int[prices.length];//store the max profit so far for the days [i,n] for i from 0 to n
int minl,maxprofit,maxr,profit;
maxprofit = ;//lower bound on profit
minl = Integer.MAX_VALUE;//minimum price so far for populating left array
for(int i = ; i < left.length; i++){
if (prices[i] < minl) minl = prices[i];//check if this price is the minimum price so far
profit = prices[i] - minl;//get the profit of selling at current price having bought at min price so far
if (profit > maxprofit) maxprofit = profit;//if the profit is greater than the profit so far, update the max profit
left[i] = maxprofit;
}
maxprofit = ;//reset maxprofit to its lower bound
maxr = Integer.MIN_VALUE;//maximum price so far for populating the right array
//same line of reasoning as the above
for(int i = left.length - ; i >= ; i--){
if (prices[i] > maxr) maxr = prices[i];
profit = maxr - prices[i];
if (profit > maxprofit) maxprofit = profit;
right[i] = maxprofit;
}
//get the best by combining the subproblems as described above
int best = ;
for(int i = ; i < prices.length - ; i++){
if (left[i] + right[i+] > best) best = left[i] + right[i+];
}
best = best > maxprofit ? best : maxprofit;
// in total 3 passes required and 2 extra arrays of size n
return best;
}
}
第二种：更厉害，泛化到了k次交易的情况 而且代码特别短
https://oj.leetcode.com/discuss/15153/a-clean-dp-solution-which-generalizes-to-k-transactions
class Solution {
public:
int maxProfit(vector<int> &prices) {
// f[k, ii] represents the max profit up until prices[ii] (Note: NOT ending with prices[ii]) using at most k transactions.
// f[k, ii] = max(f[k, ii-1], prices[ii] - prices[jj] + f[k-1, jj]) { jj in range of [0, ii-1] }
// = max(f[k, ii-1], prices[ii] + max(f[k-1, jj] - prices[jj]))
// f[0, ii] = 0; 0 times transation makes 0 profit
// f[k, 0] = 0; if there is only one price data point you can't make any money no matter how many times you can trade
if (prices.size() <= ) return ;
else {
int K = ; // number of max transation allowed
int maxProf = ;
vector<vector<int>> f(K+, vector<int>(prices.size(), ));
for (int kk = ; kk <= K; kk++) {
int tmpMax = f[kk-][] - prices[];
for (int ii = ; ii < prices.size(); ii++) {
f[kk][ii] = max(f[kk][ii-], prices[ii] + tmpMax);
tmpMax = max(tmpMax, f[kk-][ii] - prices[ii]);
maxProf = max(f[kk][ii], maxProf);
}
}
return maxProf;
}
}
};