👨?🏫 題目地址

---

無后效性

為了保證計算子問題能夠按照順序、不重復(fù)地進行，動態(tài)規(guī)劃要求已經(jīng)求解的子問題不受后續(xù)階段的影響。這個條件也被叫做「無后效性」。換言之，動態(tài)規(guī)劃對狀態(tài)空間的遍歷構(gòu)成一張有向無環(huán)圖，遍歷就是該有向無環(huán)圖的一個拓撲序。有向無環(huán)圖中的節(jié)點對應(yīng)問題中的「狀態(tài)」，圖中的邊則對應(yīng)狀態(tài)之間的「轉(zhuǎn)移」，轉(zhuǎn)移的選取就是動態(tài)規(guī)劃中的「決策」。

關(guān)鍵 1：理解題意

題目要我們找出和最大的連續(xù)子數(shù)組的值是多少，「連續(xù)」是關(guān)鍵字，連續(xù)很重要，不是子序列。

題目只要求返回結(jié)果，不要求得到最大的連續(xù)子數(shù)組是哪一個。這樣的問題通?？梢允褂谩竸討B(tài)規(guī)劃」解決。

關(guān)鍵 2：如何定義子問題（如何定義狀態(tài)）

設(shè)計狀態(tài)思路：把不確定的因素確定下來，進而把子問題定義清楚，把子問題定義得簡單。動態(tài)規(guī)劃的思想通過解決了一個一個簡單的問題，進而把簡單的問題的解組成了復(fù)雜的問題的解。

🍻 DP

public class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int[] f = new int[n];// 記錄nums[i]結(jié)尾的最大連續(xù)數(shù)組和f[0] = nums[0];int ans = f[0];for (int i = 1; i < n; i++){f[i] = Math.max(f[i - 1] + nums[i], nums[i]);ans = Math.max(ans, f[i]);}return ans;}
}

🍻 DP優(yōu)化空間

public class Solution {public int maxSubArray(int[] nums) {int pre = 0;int res = nums[0];for (int num : nums) {pre = Math.max(pre + num, num);res = Math.max(res, pre);}return res;}
}

🍻 分治

public class Solution {public int maxSubArray(int[] nums) {int len = nums.length;if (len == 0) {return 0;}return maxSubArraySum(nums, 0, len - 1);}private int maxCrossingSum(int[] nums, int left, int mid, int right) {// 一定會包含 nums[mid] 這個元素int sum = 0;int leftSum = Integer.MIN_VALUE;// 左半邊包含 nums[mid] 元素，最多可以到什么地方// 走到最邊界，看看最值是什么// 計算以 mid 結(jié)尾的最大的子數(shù)組的和for (int i = mid; i >= left; i--) {sum += nums[i];if (sum > leftSum) {leftSum = sum;}}sum = 0;int rightSum = Integer.MIN_VALUE;// 右半邊不包含 nums[mid] 元素，最多可以到什么地方// 計算以 mid+1 開始的最大的子數(shù)組的和for (int i = mid + 1; i <= right; i++) {sum += nums[i];if (sum > rightSum) {rightSum = sum;}}return leftSum + rightSum;}private int maxSubArraySum(int[] nums, int left, int right) {if (left == right) {return nums[left];}int mid = left + (right - left) / 2;return max3(maxSubArraySum(nums, left, mid),maxSubArraySum(nums, mid + 1, right),maxCrossingSum(nums, left, mid, right));}private int max3(int num1, int num2, int num3) {return Math.max(num1, Math.max(num2, num3));}
}

👨?🏫 參考地址