股票类算法题（动态规划）c++

题目描述

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

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

递推公式：

• buy = max(buy, -price[i])  （注意：根据定义 buy 是负数）

• sell = max(sell,  prices[i] + buy)

• 边界：第一天 buy = -prices[0], sell = 0，最后返回 sell 即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len<=1)
            return 0;
        int buy=-prices[0],sell=0;
        for(int i=1;i<len;i++)
        {
            buy=max(buy,-prices[i]);
            sell=max(sell,buy+prices[i]);
        }
        return sell;
    }
};

题目描述

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

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

递推公式：

• buy = max(buy, sell - price[i])

• sell = max(sell,   buy + prices[i] )

• 边界：第一天 buy = -prices[0], sell = 0，最后返回 sell 即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len<=1)
            return 0;
        int buy=-prices[0],sell=0;
        for(int i=1;i<len;i++)
        {
            buy=max(buy,sell-prices[i]);
            sell=max(sell,buy+prices[i]);
        }
        return sell;
    }
};

题目描述

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

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

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

递推公式：

• fstBuy = max(fstBuy ，  -price[i])

• fstSell = max(fstSell，fstBuy + prices[i] )

• secBuy = max(secBuy ，fstSell -price[i]) (受第一次卖出状态的影响)

• secSell = max(secSell ，secBuy + prices[i] )

• 边界：一开始 fstBuy = -prices[0]，买入后直接卖出，fstSell = 0，买入后再卖出再买入，secBuy - prices[0]，买入后再卖出再买入再卖出，secSell = 0，最后返回 secSell 。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len<=1)
            return 0;
        int fstBuy=-prices[0],secBuy=-prices[0],fstSell=0,secSell=0;
        for(int i=1;i<len;i++)
        {
            fstBuy=max(fstBuy,-prices[i]);
            fstSell=max(fstSell,fstBuy+prices[i]);
            secBuy=max(secBuy,fstSell-prices[i]);
            secSell=max(secSell,secBuy+prices[i]);
        }
        return secSell;
    }
};