风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，

转自：http://www.cnblogs.com/ranranblog/p/5845010.html

风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，数组中第i个元素（prices[i]）代表该股票第i天的股价。 假设你一开始没有股票，但有至多两次买入1股而后卖出1股的机会，并且买入前一定要先保证手上没有股票。若两次交易机会都放弃，收益为0。 设计算法，计算你能获得的最大收益。 输入数值范围：2<=n<=100,0<=prices[i]<=100

输入例子:

3,8,5,1,7,8

输出例子:

12

法一：分成两部分分别计算

 public static int getmax(int [] prices ,int start ,int end )

 {

 int max = ;

 int min = prices[start];

 for(int i=start+;i<=end;i++)

 {

 if (prices[i]-min>max)

 max = prices[i]-min;

 if (prices[i]<min)

 min = prices[i];

 }

 return max ;

 }

 /**

      * 计算你能获得的最大收益

      *

      * @param prices Prices[i]即第i天的股价

      * @return 整型

      */

     public static int calculateMax(int[] prices)

     {

     int sum = ;

     for(int i=;i<prices.length;i++)

     {

     int temp = getmax(prices,,i)+getmax(prices,i,prices.length-);

     if(temp>sum)

     sum = temp;

     }

     return sum;

     ｝

法二：利用动态规划，left[i]标识从0-i最大利润right[i] 从i到end的最大利润

 int calculateMax(vector<int> prices) {

         int n=prices.size();

         if(n<=)

             return ;

         vector<int>left(n,);

         vector<int>right(n,);

         int min=prices[];

         for(int i=;i<n;i++)

         {

             if(min>prices[i])

                 min=prices[i];

             left[i]=max(prices[i]-min,left[i-]);

         }

         int high=prices[n-];

         for(int i=n-;i>=;i--)

         {

             if(high<prices[i])

                 high=prices[i];

             right[i]=max(high-prices[i],right[i+]);

         }

         int result=;

         for(int i=;i<n;i++)

         {

             if(right[i]+left[i]>result)

                 result=right[i]+left[i];

         }

         return result;

     }

风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，的相关教程结束。