題目說明
LeetCode 53. Maximum Subarray
給一個整數陣列 nums，找出一個「連續子陣列」，使得它的總和最大，並回傳這個最大和。

範例

輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 子陣列 [4,-1,2,1] 的總和最大 = 6

解題思路（Kadane’s Algorithm）

1. 我們用一個變數 currentSum 代表「以當前元素結尾的子陣列最大和」。
2. 每次看新元素 num 時，決定要不要「繼續累加」或是「重新開始」。

• currentSum = max(num, currentSum + num)

3. 同時維護一個全域最大值 maxSum。
   貪婪法：只要一步一步做「局部最佳決策」（要不要跟前面的子陣列合併），就能得到全域最佳解。

程式碼

Java 解法

class Solution {
public int maxSubArray(int[] nums) {
int currentSum = nums[0];
int maxSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]); 
        maxSum = Math.max(maxSum, currentSum);                
    }
    return maxSum;
}

}

Python 解法

def maxSubArray(nums):
current_sum = nums[0]
max_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum

current_sum = max(num, current_sum + num)
這一行的意思就是：
num：如果乾脆「重新開始」，只取目前這個數字當起點。
current_sum + num：如果「繼續累加」，把之前的總和加上目前數字。
每一步都用數學比較（max()）去判斷，然後比較哪個大就選那個。

Java vs Python 比較

在這題裡，Java 的程式碼比較正式，必須明確宣告陣列索引、使用 Math.max。
Python 的寫法更直觀，可以用 nums[1:]直接遍歷後面元素，不需要顯式索引，整體更精簡。
但兩者的邏輯一樣：不斷決定「要不要繼續加」並更新最大值。

複雜度分析

• 時間複雜度：O(n)，只需要一次遍歷。
• 空間複雜度：O(1)，只用了兩個變數（currentSum 和 maxSum）。

心得

這題讓我更深刻理解「貪婪法」：不需要窮舉所有子陣列，只要在每一步根據當下狀況做出「繼續還是重啟」的選擇（一步一步地做局部最佳選擇），就能找到全域最大值。