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

股市的交易日

///
/// 在股市的交易日中，假设最多可进行两次买卖(即买和卖的次数均小于等于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;
        }