首页 > 代码库 > Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

2024-07-06 10:53:00   224人阅读

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) 
    {
        int n=prices.size();
        int maxpro=profit(prices,0,n-1);
        for(int i=1;i<n-1;i++)
        if(prices[i]>=prices[i-1] && prices[i]>prices[i+1])
        {
            int pro=profit(prices,0,i)+profit(prices,i+1,n-1);
            if(pro>maxpro) maxpro=pro;
        }
        return maxpro;
    }
    int profit(const vector<int>& prices,int l,int r)
    {
        if(l>=r) return 0;
        
        int low=prices[l];
        int maxpro=0;
        for(int i=l+1;i<=r;i++)
        {
            if(prices[i]-low>maxpro)
                maxpro=prices[i]-low;
            if(prices[i]<low) low=prices[i];
        }
        return maxpro;
    }
};

 


联系
我们