劍指 Offer 63. 股票的最大利潤

題意：假設(shè)把某股票的價格按照時間先后順序存儲在數(shù)組中，請問買賣該股票一次可能獲得的最大利潤是多少？

解題思路

解法：
1.分析題意，我們定義，P[n]為第n天賣出所能收獲的最大收益
2.接下來分析，這個第n天的最大收益，和什么有關(guān)系的？顯而易見，是想要知道前面n-1天，哪天的價格是最低的，在那天買入，然后在第n天賣出，就是我們所求的第n天的最大收益
3.問題轉(zhuǎn)換，求取狀態(tài)轉(zhuǎn)移方程實際為：P[n]=prices[n]-min(前面n-1天的最小價格)
4.我們定義，min為前面n-1天的最小價格，pn為第n天的最大收益，迭代求取結(jié)果即可

解題遇到的問題

無

后續(xù)需要總結(jié)學(xué)習(xí)的知識點

無

##解法1
class Solution {
    public int maxProfit(int[] prices) {
        // 分析題意，我們定義，P[n]為第n天賣出所能收獲的最大收益
        // 接下來分析，這個第n天的最大收益，和什么有關(guān)系的？顯而易見，是想要知道前面n-1天，哪天的價格是最低的，在那天買入，然后在第n天賣出，就是我們所求的第n天的最大收益
        // 問題轉(zhuǎn)換，求取狀態(tài)轉(zhuǎn)移方程實際為：P[n]=prices[n]-min(前面n-1天的最小價格)
        if (prices.length <= 1) {
            return 0;
        }
        // min為前面n-1天的最小價格,pn為第n天的最大收益
        int min = prices[0], pn = 0, max = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            pn = prices[i] - min;
            max = Math.max(pn, max);
        }
        return max;
    }
}