股市的交易日（动态规划算法）

谁借莪１个温暖的怀抱￠ 2022-05-31 12:42 122阅读 0赞

## 股市的交易日 ##

--------------------

///  
/// 在股市的交易日中，假设最多可进行两次买卖(即买和卖的次数均小于等于2)，规则是必须一笔成交后进行另一笔(即买-卖-买-卖的顺序进行)。给出一天中的股票变化序列，请写一个程序计算一天可以获得的最大收益。  
///给定价格序列prices及它的长度n，请返回最大收益。保证长度小于等于500。  
///测试样例：  
///\[10,22,5,75,65,80\]，6  
///返回：  
///87  
///

想法：

最多两次交易，前一次交易与后一次交易的结果想加，有关联，所以选用 动态规划算法

把序列分为两段  
…  
10 ||22 5 75 65 80  
10 22||5 75 65 80  
10 22 5||75 65 80  
…  
计算前一段跟后一段的最优解相加最优

**c\# 代码1**

///使用： 
    /// int[] prices = { 10,2,5,75,65,80,5,6 };
    /// int max = maxProfit2(prices, prices.Length);
    ///方法：
     static int maxProfit2(int[] prices, int n)
            {
                Console.WriteLine("maxProfit2");
                int times = 0;
                int max = 0;
                int onemax = 0, twomax = 0;
                for (int i = 0; i < n; i++)
                {
                    onemax = 0; twomax = 0;
                    for (int j2 = 0; j2 < i; j2++)
                    {
                        for (int j3 = j2; j3 < i; j3++)
                        {
                            times++;
                            int vTmp = prices[j3] - prices[j2];
                            if (vTmp > onemax)
                            {
                                onemax = vTmp;
                            }
                        }
                    }
    
                    for (int k2 = i; k2 < n; k2++)
                    {
                        for (int k3 = k2; k3 < n; k3++)
                        {
                            times++;
                            int vTmp = prices[k3] - prices[k2];
                            if (vTmp > twomax)
                            {
                                twomax = vTmp;
                            }
                        }
                    }
                    Console.WriteLine(onemax + "--"+ twomax);
                    int tmpMax = onemax + twomax;
                    if (max < tmpMax)
                    {
                        max = tmpMax;
                    }
                }
                Console.WriteLine("maxProfit2-end:" + times);
                return max;
            }

**c\# 代码2**

///使用： 
    /// int[] prices = { 10,2,5,75,65,80,5,6 };
    /// int max = maxProfit3(prices, prices.Length);
    ///方法：
    static int maxProfit3(int[] prices, int n) 
            {
                Console.WriteLine("maxProfit3");
                int max = 0;
                int times = 0;
                int onemax, twomax;
                for (int i = 0; i < n; i++)
                {
                    onemax = 0; twomax = 0;
                    for (int j = 0; j < i; j++)
                    {
                        for (int j2 = 0; j2 < j; j2++)
                        {
                            times++;
                            int tmpPri = prices[j] - prices[j2];
                            if (tmpPri > onemax)
                            {
                                onemax = tmpPri;
                            }
                        }
    
                    }
                    for (int k = i + 1; k < n; k++)
                    {
                        times++;
                        if ((prices[k] - prices[i]) > twomax)
                        {
                            twomax = prices[k] - prices[i];
                        }
                    }
                    Console.WriteLine(onemax + "--" + twomax);
                    int tmpMax = onemax + twomax;
                    if (tmpMax > max)
                    {
                        max = tmpMax;
                    }
                }
                Console.WriteLine("maxProfit3-end:" + times);
                return max;
            }