休息了一天，開始補上！

---

給你一個整數數組 nums ，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
子數組是數組中的一個連續部分。

示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子數組 [4,-1,2,1] 的和最大，為 6 。

示例 2：
輸入：nums = [1]
輸出：1

示例 3：
輸入：nums = [5,4,-1,7,8]
輸出：23

提示：
1 <= nums.length <= $10^5$
$?10^4$ <= nums[i] <= $10^4$

---

知識點：
數組、前綴和、貪心

---

解：
由于數組的元素可能是負數，與*#560. 和為K的子數組*一樣的思路，不能采用滑動窗口，因此使用前綴和
由于這題只需計算子數組元素和，無需輸出子數組本身，因此可使用int類型的變量分別存儲前綴和、最小前綴和。并在遍歷所有元素時，邊更新前綴和，邊維護最小前綴和。

以測試樣例1為例：

具體步驟：
①更新當前位置的前綴和
②計算前綴和-最小前綴和，若比res大，就更新
③更新最小前綴和
由于題目要求子數組最少包含一個元素，因此步驟②必須在③之前。

時間復雜度：$O(n)$。只遍歷了一次數組
空間復雜度：$O(1)$

class Solution {public int maxSubArray(int[] nums) {int res=Integer.MIN_VALUE;//定義變量存儲前綴和（包含當前元素）int preSum=0;//定義變量存儲最小前綴和int minPreSum=0;//遍歷每個元素，邊計算當前位置的前綴和，邊維護最小前綴和for(int num:nums){//更新當前位置的前綴和preSum+=num;//計算前綴和-最小前綴和res=Math.max(res, preSum-minPreSum);//更新最小前綴和minPreSum=Math.min(minPreSum, preSum);}return res;}
}

---

參考：
1、靈神解析