參考文獻(xiàn)：http://blog.csdn.net/li563868273/article/details/51073838 風(fēng)口之下，豬都能飛。當(dāng)今中國股市牛市，真可謂“錯過等七年”。 給你一個回顧歷史的機(jī)會，已知一支股票連續(xù)n天的價格走勢，以長度為n的整數(shù)數(shù)組表示，數(shù)組中第i個元素（prices[i]）代表該股票第i天的股價。 假設(shè)你一開始沒有股票，但有至多兩次買入1股而后賣出1股的機(jī)會，并且買入前一定要先保證手上沒有股票。若兩次交易機(jī)會都放棄，收益為0。 設(shè)計算法，計算你能獲得的最大收益。 輸入數(shù)值范圍：2<=n<=100,0<=prices[i]<=100?

輸入例子:

3,8,5,1,7,8

輸出例子:

12

解析：動態(tài)規(guī)劃思路，有0次，1次，2次機(jī)會操作股票，那么可以把數(shù)組以i為中間值分為前半段和后半段，0<=i<=n-1,dpl[i]表示從0到i-1天內(nèi)的最大收益，dpr[i]表示從第i-1天到第n-1天內(nèi)的最大收益，兩者相加可求出總的最大收益

import java.sql.ResultSet;public class Main {public static void main(String[] args) {int[] array = new int[] { 3, 8, 5, 1, 7, 8 };calculateMax3(array);}public static int calculateMax(int[] p) {int[] dpl=new int[p.length];//dpl[i]為從0開始到i的所有天中能獲得的最大的收益，可能是其中的一段時間int length=p.length;dpl[0]=0;int min=0;//min為從第min天開始買入到第i天獲得的收益int resl=0;for(int i=1;i<length;i++){if(p[i]>p[i-1]){resl=Math.max(p[i]-p[min], resl);//比較值為歷史新低到當(dāng)前天的最大收益和前i天歷史最大值dpl[i]=resl;//若第二天上漲，有可能該天到買入收益最大，也有可能是股票回升//若股票回升，則還是為前i天最大值，即前i天最大收益仍為第min天到第某天}else {//若第二天下跌，則看是否跌出谷底，//若沒有跌出谷底，則仍為前i-1天最大收益//若跌出谷底則重新計算最小值，從該天算后面的收益dpl[i]=dpl[i-1];if(p[i]<p[min]){min=i;}}}int[] dpr=new int[length];dpr[length-1]=0;int resr=0;int max=length-1;for(int i=length-2;i>=0;i--){if(p[i]<p[i+1]){resr=Math.max(p[max]-p[i], resr);dpr[i]=resr;}else {dpr[i]=dpr[i+1];if(p[i]>p[max]){max=i;}}}int res =0;for(int i=0;i<length;i++){res=Math.max((dpl[i]+dpr[i]), res);}System.out.println(res);return res;}/*** 計算你能獲得的最大收益** @param prices* Prices[i]即第i天的股價* @return 整型*/public static int calculateMax2(int[] prices) {int firstBuy = Integer.MIN_VALUE, firstSell = 0;int secondBuy = Integer.MIN_VALUE, secondSell = 0;for (int curPrice : prices) {firstBuy = Math.max(firstBuy, -curPrice);firstSell = Math.max(firstSell, firstBuy + curPrice);secondBuy = Math.max(secondBuy, firstSell - curPrice);secondSell = Math.max(secondSell, secondBuy + curPrice);System.out.println("firstBuy: " + firstBuy + ", firstSell: "+ firstSell + ", secondBuy: " + secondBuy+ ", secondSell: " + secondSell);}return secondSell;} // 來自http://blog.csdn.net/li563868273/article/details/51073838public static int calculateMax3(int[] prices) {// 記錄[0..i]之間的最大收益int[] dpl = new int[prices.length];// 記錄[i...length-1]的最大收益int[] dpr = new int[prices.length];dpl[0] = 0;// 第一個肯定賦值為0int minI = 0;// 掃描一次左邊System.out.print("dpl[0]=0, ");for (int i = 1; i < dpl.length; i++) {// 如果大于等于if (prices[i] > prices[i - 1]) {dpl[i] = Math.max(prices[i] - prices[minI], dpl[i - 1]);} else {dpl[i] = dpl[i - 1];if (prices[i] < prices[minI])minI = i;}System.out.print("dpl[" + i + "]=" + dpl[i] + ", ");}System.out.println();// 最后一個肯定賦值為0dpr[prices.length - 1] = 0;int maxI = prices.length - 1;System.out.print("dpr[" + (prices.length - 1) + "]=0, ");for (int i = prices.length - 2; i >= 0; i--) {// 從右到左掃描一遍填充dpr數(shù)組,和從左邊掃描一樣if (prices[i] < prices[i + 1]) {dpr[i] = Math.max(prices[maxI] - prices[i], dpr[i + 1]);} else {dpr[i] = dpr[i + 1];if (prices[i] > prices[maxI]) {maxI = i;}}System.out.print("dpr[" + i + "]=" + dpr[i] + ", ");}System.out.println();int res = 0;for (int i = 0; i < prices.length - 1; i++) { // 比較得出最大值res = Math.max(dpl[i] + dpr[i], res);System.out.println("dpl[" + i + "]=" + dpl[i] + ",dpr[" + i + "]="+ dpr[i] + ",res=" + res);}return res;} }

總結(jié)

以上是生活随笔為你收集整理的风口上的猪-中国牛市的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。