首页 > 代码库 > 风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，
风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续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
法一：分成两部分分别计算
1 public static int getmax(int [] prices ,int start ,int end ) 2 { 3 int max = 0; 4 int min = prices[start]; 5 for(int i=start+1;i<=end;i++) 6 { 7 if (prices[i]-min>max) 8 max = prices[i]-min; 9 if (prices[i]<min)10 min = prices[i];11 }12 return max ;13 }14 /**15 * 计算你能获得的最大收益16 * 17 * @param prices Prices[i]即第i天的股价18 * @return 整型19 */20 public static int calculateMax(int[] prices)21 {22 int sum = 0;23 24 for(int i=1;i<prices.length;i++)25 {26 int temp = getmax(prices,0,i)+getmax(prices,i,prices.length-1);27 if(temp>sum)28 sum = temp;29 }30 return sum;31 ｝
法二：利用动态规划，left[i]标识从0-i最大利润right[i] 从i到end的最大利润1 int calculateMax(vector<int> prices) { 2 int n=prices.size(); 3 if(n<=1) 4 return 0; 5 vector<int>left(n,0); 6 vector<int>right(n,0); 7 int min=prices[0]; 8 for(int i=1;i<n;i++) 9 {10 if(min>prices[i])11 min=prices[i];12 left[i]=max(prices[i]-min,left[i-1]);13 }14 int high=prices[n-1];15 for(int i=n-2;i>=0;i--)16 {17 if(high<prices[i])18 high=prices[i];19 right[i]=max(high-prices[i],right[i+1]);20 }21 int result=0;22 for(int i=0;i<n;i++)23 {24 if(right[i]+left[i]>result)25 result=right[i]+left[i];26 }27 return result;28 }
风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。