Best Time to Buy and Sell Stockベストタイム買い売り株(1回買い売り)@LeetCode

タイトル:
株を売るのに最適な時間:あなたは1つの配列が株のi日目の価格を保存して、今あなたは1回の購入と売ることしかできなくて、どのように最も儲けることができます
考え方:
min最小購入価格を記録する
maxProfitレコード最大利益
arrayを巡り、最小購入価格を更新し、最大利益を計算します.

package Level2;

/**
 * Best Time to Buy and Sell Stock 
 * 
 * Say you have an array for which the ith
 * element is the price of a given stock on day i.
 * 
 * If you were only permitted to complete at most one transaction (ie, buy one
 * and sell one share of the stock), design an algorithm to find the maximum
 * profit.
 */
public class S121 {

	public static void main(String[] args) {

	}
	
	public int maxProfit(int[] prices) {
		//      prices     
		if(prices.length == 0){
			return 0;
		}
        int min = prices[0];		//         index
        int maxProfit = 0;			//     profit
        
        for(int i=1; i<prices.length; i++){
        	//        
        	if(prices[i] < min){
        		min = prices[i];
        	}
        	
        	//       
        	int currentProfit = prices[i] - min;
        	//             ，      
        	if(currentProfit > maxProfit){
        		maxProfit = currentProfit;
        	}
        }
        
        return maxProfit;
    }

}

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }
        int minBuy = prices[0];
        int maxProfit = 0;
        
        for(int i=0; i<prices.length; i++){
            minBuy = Math.min(minBuy, prices[i]);
            maxProfit = Math.max(maxProfit, prices[i]-minBuy);
        }
        return maxProfit;
    }
}

「ローカル最適化とグローバル最適化の解法」を使用します.
構想は2つの変数を維持することであり、1つはこれまでで最も良い取引であり、もう1つは現在の1日で販売された最適な取引(すなわち局所的に最も優れている)である.繰返し式は、local[i+1]=max(local[i]+prices[i+1]-price[i],0)、global[i+1]=max(local[i+1],global[i])である.このように1回のスキャンで結果が得られ,時間的複雑度はO(n)であった.空間にはO(1)という2つの変数しか必要ありません.
http://blog.csdn.net/linhuanmars/article/details/23162793
注意すべき点は2つあります.
1はi日目に購入し、i+1日目に販売し、i+1日目に購入し、i+2日目に販売する.i日目に購入してi+2日目に販売するのと同じである:p[i+2]-p[i]=-p[i]+p[i+1]-p[i+1]+p[i+2]
2出没2日間の差を計算すると、diff 1,diff 2,diff 3はmaximum subarrayの問題に変換されます.

public class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len == 0){
            return 0;
        }
        int[] local = new int[len+1];
        int[] global = new int[len+1];
        
        local[0] = 0;
        global[0] = 0;
        for(int i=1; i<len; i++) {
            int diff = prices[i] - prices[i-1];
            local[i] = Math.max(local[i-1]+diff, Math.max(diff, 0));
            global[i] = Math.max(global[i-1], local[i]);
        }
        
        return global[len-1];
    }
}