【題目描述】
????????給定一個數組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子賣出該股票。設計一個算法來計算你所能獲取的最大利潤。返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0?
【題目鏈接】. - 力扣（LeetCode）
【解題代碼】
public class MaxProfit {public static void main(String[] args) {//int[] prices = {7, 1, 5, 3, 6, 4};int[] prices = {7, 6, 4, 3, 1};System.out.println("The result is: " + new MaxProfit().maxProfit(prices));}public int maxProfit(int[] prices) {// 定義動態規劃中間過程數組int dp[] = new int[prices.length];// 初始化歷史最低股價int minPrice = prices[0];// 初始化歷史最大收益int maxProfit = 0;for (int i = 1; i < prices.length; i++) {// 當天最大收益等于當前股價減去初始化歷史最低股價dp[i] = prices[i] - minPrice;// 當天股價如果低于歷史最低股價，更新歷史最新股價minPrice = Math.min(minPrice, prices[i]);// 保存到當天為止，最大的收益maxProfit = Math.max(maxProfit, dp[i]);}return maxProfit;}}【解題步驟】
- 從題目描述可以得知，此問題是要根據歷史依次往后計算當天的最大股票收益值，很自然的想到采用動態規劃的算法，因此照例定義一個動態規劃數組
// 定義動態規劃中間過程數組 int dp[] = new int[prices.length]; - 再次根據題目可知，當天收益等于當天的股價減去歷史最低股價。然后依次保存最大的收益即可，因此需要定義歷史最低股價和歷史最大收益兩個變量
// 初始化歷史最低股價 int minPrice = prices[0]; // 初始化歷史最大收益 int maxProfit = 0; - 接下來就是按照動態規劃的算法，依次計算中間過程，并不斷更新歷史最低股價和歷史最大收益即可
// 依次計算每天的最大收益 for (int i = 1; i < prices.length; i++) {// 當天最大收益等于當前股價減去初始化歷史最低股價dp[i] = prices[i] - minPrice;// 當天股價如果低于歷史最低股價，更新歷史最新股價minPrice = Math.min(minPrice, prices[i]);// 保存到當天為止，最大的收益maxProfit = Math.max(maxProfit, dp[i]); } - 最后返回最大收益值即可
return maxProfit;
【思路總結】
- 動態規劃算法是數據結構中一個很重要的算法，另外一般學校里教的都很淺薄，程序員一定要自學掌握其算法脈絡，并能學會靈活運用；
- 動態規劃數組的做法一般都是定義個一維或者二維數據，依次遞推計算當前數值；
- 無后效性，遞推算法一般只需要考慮眼前最近一層，其它層一定不需要考慮。“未來與過去無關”
)
