題目連結(https://leetcode.com/problems/maximum-subarray/description/)

Given an integer array nums, find the subarray with the largest sum, and return its sum.

演算法教科書會看到的經典題，程式設計師必會題！

1. Repeat（題目重複確認)

• 輸入：整數陣列 nums
• 輸出：找具有最大總和的子陣列，並回傳 sum
• 前提：
  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 規模出大一點比較有挑戰性

2. Examples（舉例確認理解）

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.

3. Approach（解題思路）

方法 1：Divide and Conquer

關鍵在於：最大子陣列可能出現在三個位置：

1. 左半部
2. 右半部
3. 跨越中點（左半部分 + 右半部分）

• 時間複雜度：O(n log n)
  • 遞迴樹高度：log n
  • 每層需要 O(n) 時間計算跨越和
  • T(n) = 2T(n/2) + O(n) = O(n log n)
  • 雖然比較久，但這是學 Divide and Conquer 的好例子
• 空間複雜度：O(log n)
  • 遞迴呼叫堆疊深度

方法 2：DP

• dp[i]= 以 i 作為 結尾 的最大子陣列和（必須包含 nums[i]）。
• 轉移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])
• 實作技巧：
  • 只需要前一個 dp[i-1]，可用兩個變數：currentSum、maxSum，空間 O(1)。
  • 全為負數 也可處理（初始化用 nums[0]，不要從 0 開始）。
  • 時間複雜度：O(n)
  • 空間複雜度：O(1)

4. Code（C++）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return divide_conquer(nums, 0, nums.size() - 1);    
    }

    int divide_conquer(vector<int>& nums, int l, int r){
        if(l == r) return nums[l]; //不能設定成0，得要使用更新後的l
        int m = l + (r-l)/2;

        int leftmax = divide_conquer(nums, l, m);
        int rightmax = divide_conquer(nums, m+1, r);
        int crossmax = cross_sum(nums, l, m, r);

        return max({leftmax, rightmax, crossmax});
    }

    int cross_sum(vector<int>& nums, int l, int m, int r){
        int leftsum = nums[m];
        int sum = nums[m];
        for(int i = m - 1; i >= l; i--){
            sum += nums[i];
            leftsum = max(leftsum, sum);
        }

        int rightsum = nums[m+1];
        int sum2 = nums[m+1];
        for(int i = m + 2; i <= r; i++){
            sum2 += nums[i];
            rightsum = max(rightsum, sum2);
        }
        return leftsum + rightsum;
    } 
};

# DP(Kadane's Algorithm)
// O(n) 解法 - 更優！
int maxSubArray(vector<int>& nums) {
    int maxsum = nums[0];
    int currentsum = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        currentsum = max(nums[i], currentsum + nums[i]);
        maxsum = max(maxsum, currentsum);
    }
    
    return maxsum;
}

5. Test 範例

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

初始化：
currentSum = -2
maxSum = -2

i=1: nums[1]=1
currentSum = max(1, -2+1) = 1
maxSum = max(-2, 1) = 1

i=2: nums[2]=-3
currentSum = max(-3, 1-3) = -2
maxSum = max(1, -2) = 1

i=3: nums[3]=4
currentSum = max(4, -2+4) = 4
maxSum = max(1, 4) = 4

i=4: nums[4]=-1
currentSum = max(-1, 4-1) = 3
maxSum = max(4, 3) = 4

i=5: nums[5]=2
currentSum = max(2, 3+2) = 5
maxSum = max(4, 5) = 5

i=6: nums[6]=1
currentSum = max(1, 5+1) = 6
maxSum = max(5, 6) = 6

...
最後答案 = 6

6. 相關題目與延伸概念

• 918. Maximum Sum Circular Subarray（環狀版本，需同時算非跨界與「總和−最小子陣列」）
• 152. Maximum Product Subarray（乘積版本，需同時維護最大/最小乘積）
• 560. Subarray Sum Equals K（前綴和 + HashMap 計數）

7. 補充：語法＆注意事項

ps. 部分內容經 AI 協助整理