see {http://www.jianshu.com/p/ba2db41cc1c9?utm_campaign=maleskine&utm_content=note&utm_medium=pc_all_hots&utm_source=recommendation} 规则： 一只股票，上午9时开盘，下午16点收盘，每个时间点对应一个价格。 1.当天什么时间买入，什么时间卖出可获得最大利润。 2.只能买卖一次（额外规则） 3.相同利润下时间段最短的优先

StockTrading.java

/**
 * see {http://www.jianshu.com/p/ba2db41cc1c9?utm_campaign=maleskine&utm_content=note&utm_medium=pc_all_hots&utm_source=recommendation}
 * 规则：
 * 一只股票，上午9时开盘，下午16点收盘，每个时间点对应一个价格。
 * 1.当天什么时间买入，什么时间卖出可获得最大利润。
 * 2.只能买卖一次（额外规则）
 * 3.相同利润下时间段最短的优先
 *
 * @author fanhl
 */
public class StockTrading {
    private static int[] priceArray = {12, 11, 20, 32, 45, 8, 9, 11};
    private static int[] priceArray2 = {12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 99, 20, 32, 45, 8, 9, 12, 11, 20, 32, 72, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 12, 11, 20, 32, 45, 8, 9, 11};

    public static void main(String[] args) {
        long time1 = System.currentTimeMillis();
        System.out.println(time1);
        for (int i = 0; i < 1000000; i++) {
            findBestTime(priceArray);
        }
        long time2 = System.currentTimeMillis();
        System.out.println(time2 - time1);
        for (int i = 0; i < 1000000; i++) {
            getBestTime(priceArray);
        }
        long time3 = System.currentTimeMillis();
        System.out.println(time3 - time2);
    }

    private static void findBestTime(int[] priceArray) {
        //买入索引
        int buyTime = 0;
        //卖出索引
        int soldTime = 0;
        //卖出值-买入值的利润
        int profit = 0;

        //以下只算当前部分的最大利润
        int tempBuyTime = 0;
        int tempSoldTime = 0;
        int tempProfit = 0;

        for (int i = 0; i < priceArray.length - 1; i++) {
            int priceOffset = priceArray[i + 1] - priceArray[i];
            if (priceOffset >= 0) {
                tempSoldTime += 1;
                tempProfit += priceOffset;
            } else {
                if (tempProfit > profit) {
                    buyTime = tempBuyTime;
                    soldTime = tempSoldTime;
                    profit = tempProfit;
                }

                if (tempProfit > 0) {
                    tempSoldTime += 1;
                    tempProfit += priceOffset;
                } else {
                    tempSoldTime += 1;
                    tempBuyTime = tempSoldTime;
                    tempProfit = 0;
                }
            }

        }

//        System.out.println("Buy:" + (9 + buyTime) + " Sold:" + (9 + soldTime));
//        System.out.println("Buy:" + buyTime + " Sold:" + soldTime);
    }

    private static void getBestTime(int[] priceArray) {
        int initBuy = 0; // 假设在9点时买入
        int initSold = 1; // 假设10点卖出
//        int[] timeArray = {9,  10, 11, 12, 13, 14, 15, 16};
        int tempValue = priceArray[1] - priceArray[0];
        for (int i = 0; i < priceArray.length; i++) {
            for (int j = i + 1; j < priceArray.length; j++) {
                // 如果当前利润比之前大，则替换临时变量tempValue，并更新买入卖出时机
                if (priceArray[j] - priceArray[i] > tempValue) {
                    tempValue = priceArray[j] - priceArray[i];
                    initBuy = i;
                    initSold = j;
                }
            }
        }
//        int bestBuyTime = timeArray[initBuy];
//        int bestSoldTime = timeArray[initSold];

//        System.out.println("Buy:" + (9 + initBuy) + " Sold:" + (9 + initSold));
//        System.out.println("Buy:" + initBuy + " Sold:" + initSold);
    }
}