3,8,5,1,7,8
12
参考一楼,LeetCode经典 public class Solution { /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ public int calculateMax(int[] prices) { //王牌dp 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); } return secondSell; } }
//用dp[i]存从0到i天内买一次股票最多赚多少钱, //用dp2[i]存从第i天到最后一天买一次股票最多赚多少钱 //最大收益为MAX(dp[i] + dp2[i] public class Solution { /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ public int calculateMax(int[] prices) { int[] dp = new int[prices.length]; int[] dp2 = new int[prices.length]; int min = prices[0]; for(int i = 1; i < prices.length; i++){ if(prices[i] - min > dp[i - 1]){ dp[i] = prices[i] - min; }else { dp[i] = dp[i - 1]; } min = min < prices[i] ? min : prices[i]; } int max = prices[prices.length - 1]; for(int i = prices.length - 2; i >= 0; i--){ if(max - prices[i] > dp2[i + 1]){ dp2[i] = max - prices[i]; }else { dp2[i] = dp2[i + 1]; } max = max > prices[i] ? max : prices[i]; } int res = 0; for(int i = 0; i < prices.length; i++){ res = res > dp[i] + dp2[i] ? res : dp[i] + dp2[i]; } return res; } }
public int calculateMax(int[] prices) { int firstBuy = Integer.MAX_VALUE;//第一次买入的价格 // 接下来都是买入卖出之后的收益 int afterFirstSell = 0; int afterSecondBuy = Integer.MIN_VALUE; int afterSecondSell = 0; for (int curPrice: prices){ //第一次买入的价格应该是越小越好,最好是负数,倒贴钱 firstBuy = Math.min(firstBuy, curPrice); //第一次卖出后的收益,等于当前价格减去第一次买入价格,越高越好 afterFirstSell = Math.max(afterFirstSell, curPrice - firstBuy); //第二次买入后的收益,等于第一次卖出后的收益减去当前价格,越高越好 afterSecondBuy = Math.max(afterSecondBuy, afterFirstSell - curPrice); //第二次卖出后的收益,等于第二次买入后的收益加上当前价格,越高越好 afterSecondSell = Math.max(afterSecondSell, afterSecondBuy + curPrice); } return afterSecondSell; }自认为比最高票答案更加容易理解。
把代码简化了一些,看着比较舒畅。 public class Solution { /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ public int calculateMax(int[] prices) { int sum = 0,temp; for(int i=0; i<prices.length; i++){ temp = getMax(prices,0,i) + getMax(prices,i,prices.length-1); if(temp > sum) sum = temp; } return sum; } // 求最大start到end之间的最大利润函数 public int getMax(int[] prices, int start, int end){ int max = 0; int min = prices[start]; for(int i=start+1; i<=end; i++){ if(prices[i] < min) min = prices[i]; if(prices[i]-min > max) max = prices[i] - min; } return max; } }
/** *求局部最优解 */ public int calculateMax(int[] prices) { // TODO Auto-generated method stub if(prices==null||prices.length<2) return 0; int len=prices.length; int rest = 0; for(int i=1;i<len;i++){ int sum1 = 0; int sum2 = 0; for(int j = 0; j <=i; j++){ for(int t=j+1;t<=i;t++){ if(prices[t] - prices[j] >sum1){ sum1 = prices[t] - prices[j]; } } } if(i+1 < len){ for(int j2=i+1; j2 < len; j2++){ for(int t=j2+1;t<len;t++){ if(prices[t] - prices[j2] >sum2){ sum2 = prices[t] - prices[j2]; } } } } if(sum1 + sum2 >rest){ rest = sum1 + sum2; } } return rest; }