风口的猪-中国牛市

参考一楼，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;
    
    }