最大子序和分治

最大子序和（Maximum Subarray Problem）是一個經典的動態規劃問題，其目標是找到一個數組中的最大子序和。子序和是指數組中連續元素的 sum。例如，對於數組 [2, 11, -4, 13, -5, 5]，其最大子序和為 11 + -4 + 13 + -5 + 5 = 10。

分治是一種算法設計範式，它將問題分解為更小的、相似的子問題，直到達到最簡單的子問題，然後通過組合這些子問題的解決方案來解決原始問題。對於最大子序和問題，我們可以使用分治策略來設計一個高效的算法。

下面是一個使用分治策略解決最大子序和問題的算法：

1. 首先，我們定義一個遞歸函式 maxSubArray，它接受一個數組 nums 和一個開始索引 start 以及結束索引 end 作為參數。

2. 我們通過以下步驟來解決這個問題：

   • 如果 start == end，那么子問題的答案就是數組 nums 中的單個元素。
   • 否則，我們找到中間索引 mid = (start + end) / 2，並將子問題劃分為兩個更小的子問題。
   • 我們遞歸地解決左半部分和右半部分的問題，分別計算它們的最大子序和。
   • 我們比較左半部分和右半部分的結果與直接在 nums[start...end] 上計算的最大子序和。這個可以通過從 nums[start] 開始累加和來計算，同時維護一個當前最大值。
   • 我們返回這三個值中的最大值作為子問題的答案。

下面是偽代碼：

def maxSubArray(nums, start, end):
    if start == end:
        return nums[start]
    mid = (start + end) // 2
    left_max = maxSubArray(nums, start, mid)
    right_max = maxSubArray(nums, mid + 1, end)
    current_max = helper(nums, start, end)
    return max(left_max, right_max, current_max)

def helper(nums, start, end):
    current_sum = nums[start]
    max_ending_here = nums[start]
    for i in range(start + 1, end + 1):
        current_sum = max(current_sum + nums[i], 0)
        max_ending_here = max(max_ending_here, current_sum)
    return max_ending_here

這個算法的時間複雜度為 O(n log n)，因為每個元素都會被訪問 O(log n) 次。空間複雜度為 O(n)，因為遞歸調用棧的大小與數組的大小成正比。

在實際套用中，通常使用 Kadane's algorithm 來解決最大子序和問題，它的時間複雜度為 O(n)，空間複雜度為 O(1)，因為它是使用動態規劃線上性時間內解決的。