Best Time to Buy and Sell Stock III

  1. 云栖社区>
  2. 博客>
  3. 正文

Best Time to Buy and Sell Stock III

指尖的舞曲 2014-11-29 11:55:00 浏览256
展开阅读全文

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://www.cnblogs.com/springfor/p/3877068.html

根据题目要求,最多进行两次买卖股票,而且手中不能有2只股票,就是不能连续两次买入操作。

所以,两次交易必须是分布在2各区间内,也就是动作为:买入卖出,买入卖出。

进而,我们可以划分为2个区间[0,i]和[i,len-1],i可以取0~len-1。

那么两次买卖的最大利润为:在两个区间的最大利益和的最大利润。

一次划分的最大利益为:Profit[i] = MaxProfit(区间[0,i]) + MaxProfit(区间[i,len-1]);

最终的最大利润为:MaxProfit(Profit[0], Profit[1], Profit[2], ... , Profit[len-1])。

 

C++实现代码:

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if(prices.empty())
            return 0;
        int n=prices.size();
        int i;
        int low=prices[0];
        int left[n];
        left[0]=0;
        for(i=1;i<n;i++)
        {
            low=min(low,prices[i-1]);
            left[i]=max(left[i-1],prices[i]-low);
        }
        int high=prices[n-1];
        int right[n];
        right[n-1]=0;
        for(i=n-2;i>=0;i--)
        {
            high=max(high,prices[i+1]);
            right[i]=max(right[i+1],high-prices[i]);
        }
        int maxSum=0;
        for(i=0;i<n;i++)
        {
            maxSum=max(maxSum,left[i]+right[i]);
        }
        return maxSum;
    }
};

int main()
{
    Solution s;
    vector<int> vec={1,4,6,8,3,5,9,3,6};
    cout<<s.maxProfit(vec)<<endl;
}

 

网友评论

登录后评论
0/500
评论
指尖的舞曲
+ 关注