題目
#

leetcode 53 - Maximum Subarray (題目說明請點連結)

題目簡述
#

給一個整數陣列 nums，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），並返回其最大和。

範例
#

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

解題思路
#

這題要求我們找到一個具有最大和的連續子陣列。我們可以使用 找最大子數列做法 來解決這個問題，通過維護一個當前和變數，在遇到負數時重置為 0，並持續更新最大和。

解法
#

初始化當前和 total 為 0，最大和 res 為陣列第一個元素
遍歷陣列中的每個元素
如果當前和為負數，重置為 0（因為負數會減少後續子陣列的和）
將當前元素加入當前和，並更新最大和
返回最大和

步驟
#

初始化變數：
- total = 0：當前子陣列的和
- res = nums[0]：最大子陣列和，初始為第一個元素
遍歷陣列：
- 如果當前和為負數，重置為 0
- 將當前元素加入當前和
- 更新最大和
返回結果：
- 返回最大子陣列和

例子說明
#

nums = [-2,1,-3,4,-1,2,1,-5,4]

步驟	當前元素	當前和 (total)	最大和 (res)	操作說明
初始化	-	0	-2	`res = nums[0] = -2`
i=0	-2	0	-2	`total < 0`，重置為 0，`total = -2`，`res = max(-2, -2) = -2`
i=1	1	1	1	`total = 1`，`res = max(-2, 1) = 1`
i=2	-3	-2	1	`total = -2`，`res = max(1, -2) = 1`
i=3	4	4	4	`total < 0`，重置為 0，`total = 4`，`res = max(1, 4) = 4`
i=4	-1	3	4	`total = 3`，`res = max(4, 3) = 4`
i=5	2	5	5	`total = 5`，`res = max(4, 5) = 5`
i=6	1	6	6	`total = 6`，`res = max(5, 6) = 6`
i=7	-5	1	6	`total = 1`，`res = max(6, 1) = 6`
i=8	4	5	6	`total = 5`，`res = max(6, 5) = 6`

最大子陣列： [4,-1,2,1]，和為 6

完整程式碼
#

java

class Solution {
    public int maxSubArray(int[] nums) {
        int total = 0;
        int res = nums[0];

        for (int n : nums) {
            // 如果當前和為負數，重置為 0
            if (total < 0) {
                total = 0;
            }

            // 將當前元素加入當前和
            total += n;
            // 更新最大和
            res = Math.max(res, total);
        }

        return res;
    }
}