力扣-买卖股票的最佳时机3

标签：买卖 int 力扣 sell1 最佳时机 buy1 buy2 prices sell2

1.问题

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

实例1：

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

实例2：

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

实例3：

输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

2.说明

输入说明：

首先输入prices数组元素数目n，然后输入n个整数

输出说明：

输出一个整数

3.范例 输入： 8 3 3 5 0 0 3 1 4 输出： 6 4.思路 相比于买卖股票的最佳时机1和2，本题增加了交易次数的限制，智能交易两次，因此无法使用贪心算法。 本题思路和买卖股票的最佳时机1差不多，只是增加了1次的交易，因此有两种交易状态，buy1、buy2、sell1、sell2，其状态转移方程： buy1 = max(buy1 , 0 - prices[i]) sell1 = max(sell1 , buy1 + princes[i]) buy2 = max(buy2 , sell1 - prices[i]) sell2 = max(sell2 , buy2 + prices[i]) 边界问题：第一次交易，buy1=-prices[0]，sell1=0，相当于当天买当天卖；第二次交易，buy2=sell1 - prices[0]，sell2=0，相当于和第一次交易在同一天，也是第一次交易后买入和卖出，最后返回sell2即为最终总收益。 5.代码

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        if(prices.size()==0)
            return 0;
        int buy1=-prices[0];
        int sell1=0;
        int buy2=-prices[0];
        int sell2=0;
        for(int i=1;i<prices.size();i++)
        {
            buy1=max(buy1,-prices[i]);
            sell1=max(sell1,buy1+prices[i]);
            buy2=max(buy2,sell1-prices[i]);
            sell2=max(sell2,buy2+prices[i]);
        }
        return sell2;
    }
};
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    cin>>n;
    vector<int> prices;
    int data;
    for(int i=0;i<n;i++)
    {
        cin>>data;
        prices.push_back(data);
    }
    int res=Solution().maxProfit(prices);
    cout<<res<<endl;
    return 0;
}

 

               

标签：买卖,int,力扣,sell1,最佳时机,buy1,buy2,prices,sell2
From： https://www.cnblogs.com/ohye/p/17698618.html