給出一只股票的價(jià)格，要求給出最佳買(mǎi)入和賣(mài)出價(jià)格，使得收益最大。

示例：

輸入: [7,1,5,3,6,4]

輸出: 5

解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出，最大利潤(rùn) = 6-1 = 5 。

分析：

題目的要求是要找到前面的某一個(gè)極小值，后面的一個(gè)極大值，使得極大值與極小值的差最大。問(wèn)題解法有二：

其一，通過(guò)兩次循環(huán)，暴力計(jì)算每個(gè)買(mǎi)入點(diǎn)和賣(mài)出點(diǎn)的差，計(jì)算最大值。

int[] values = new int[]{7, 1, 5, 3, 6, 4};
int profit = 0;
int buyDate = -1;
int sellDate = -1;
for (int i = 0; i < values.length - 1; i++){
    for (int j = i+1; j  profit){
            buyDate = i;
            sellDate = j;
            profit = values[j] - values[i];
        }
    }
}

其二，通過(guò)動(dòng)態(tài)規(guī)劃的方法，一次循環(huán)搞定最大利潤(rùn)的計(jì)算。

每個(gè)位置的最大利潤(rùn)我們用dp[i]表示，則dp[i] = max(price[i] – min, dp[i-1]);

如果我們只是計(jì)算最大利潤(rùn)，那么可以簡(jiǎn)化為dp[i] = max(price[i] – min, maxProfit)

int maxProfit = 0, min = Integer.MAX_VALUE;
for(int i = 0; i < values.length; i++){
    if(values[i]  maxProfit)
        // 收益變大，更新最大收益
        maxProfit = values[i] - min;
}

解法一O(n^2), 解法二O(n)，顯然解法二更優(yōu)。