最大子數組和（Maximum Subarray Sum）是一個經典且高頻的數組算法考點，這個問題看似簡單——從一個整數數組中找到和最大的連續子數組，但暴力求解的效率極低。Kadane算法（卡丹算法）作為專門解決此問題的高效方法，能在$O(n)$時間內完成求解，是動態規劃思想的典型應用。本文我將深入解析Kadane算法的核心原理、實現細節、變種拓展及實際應用，結合Java代碼示例，幫你徹底掌握這一高效算法。

一、問題定義與暴力解法

1.1 問題描述

給定一個整數數組nums（可能包含負數），找到一個連續子數組（至少包含一個元素），使得該子數組的和最大，返回這個最大和。

例如：

• 輸入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
• 輸出：6（對應子數組[4, -1, 2, 1]）

1.2 暴力解法的低效性

最直觀的思路是枚舉所有可能的子數組，計算其和并記錄最大值：

// 暴力解法：枚舉所有子數組
public int maxSubArrayBruteForce(int[] nums) {int maxSum = Integer.MIN_VALUE;int n = nums.length;for (int i = 0; i < n; i++) {  // 子數組起點int currentSum = 0;for (int j = i; j < n; j++) {  // 子數組終點currentSum += nums[j];maxSum = Math.max(maxSum, currentSum);}}return maxSum;
}

• 時間復雜度：$O(n^2)$（嵌套循環枚舉所有子數組）。
• 局限性：當n超過$10^4$時，會因超時無法通過測試，必須尋找更高效的算法。

二、Kadane算法的核心原理

2.1 動態規劃思想的應用

Kadane算法的本質是動態規劃，其核心是用局部最優推導全局最優：

• 定義dp[i]為“以nums[i]為結尾的最大子數組和”。
• 對于每個元素nums[i]，有兩種選擇：
  1. 將nums[i]加入之前的子數組（即dp[i-1] + nums[i]）。
  2. 以nums[i]為起點重新開始一個子數組（即nums[i]）。
• 因此，狀態轉移方程為：
  dp[i] = max(nums[i], dp[i-1] + nums[i])
• 全局最大和即為所有dp[i]中的最大值。

2.2 優化空間復雜度

由于dp[i]僅依賴于dp[i-1]，無需存儲整個dp數組，可改用一個變量currentMax記錄當前值，將空間復雜度從$O(n)$優化至$O(1)$：

1. 初始化currentMax = nums[0]（以第一個元素為結尾的子數組和），maxSum = nums[0]（全局最大值）。
2. 從第二個元素開始遍歷：
   • currentMax = max(nums[i], currentMax + nums[i])（更新局部最優）。
   • maxSum = max(maxSum, currentMax)（更新全局最優）。
3. 遍歷結束后，maxSum即為結果。

三、Kadane算法的Java實現

3.1 基礎版本（處理所有情況）

public class KadaneAlgorithm {public int maxSubArray(int[] nums) {if (nums == null || nums.length == 0) {return 0;  // 邊界處理：空數組}int currentMax = nums[0];  // 以當前元素為結尾的最大子數組和int maxSum = nums[0];      // 全局最大子數組和for (int i = 1; i < nums.length; i++) {// 選擇：加入之前的子數組 或 重新開始currentMax = Math.max(nums[i], currentMax + nums[i]);// 更新全局最大值maxSum = Math.max(maxSum, currentMax);}return maxSum;}public static void main(String[] args) {KadaneAlgorithm solution = new KadaneAlgorithm();int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};System.out.println(solution.maxSubArray(nums));  // 輸出 6}
}

3.2 算法正確性驗證

以示例nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]為例，分步驗證：

索引i	nums[i]	currentMax（局部最優）	maxSum（全局最優）
0	-2	-2	-2
1	1	max(1, -2+1)=1	max(-2, 1)=1
2	-3	max(-3, 1-3)=-2	max(1, -2)=1
3	4	max(4, -2+4)=4	max(1, 4)=4
4	-1	max(-1, 4-1)=3	max(4, 3)=4
5	2	max(2, 3+2)=5	max(4, 5)=5
6	1	max(1, 5+1)=6	max(5, 6)=6
7	-5	max(-5, 6-5)=1	max(6, 1)=6
8	4	max(4, 1+4)=5	max(6, 5)=6

最終maxSum=6，與預期結果一致，驗證了算法的正確性。

四、Kadane算法的變種與拓展

4.1 變種1：輸出最大子數組的起止索引

除了最大和，有時需要返回子數組的具體位置（起點和終點索引）。只需在更新currentMax和maxSum時，同步記錄索引：

public int[] maxSubArrayWithIndex(int[] nums) {if (nums == null || nums.length == 0) {return new int[]{-1, -1};  // 空數組返回無效索引}int currentMax = nums[0];int maxSum = nums[0];int start = 0, end = 0;  // 當前子數組起止索引int tempStart = 0;       // 臨時起點（用于重新開始子數組時更新）for (int i = 1; i < nums.length; i++) {if (nums[i] > currentMax + nums[i]) {// 重新開始子數組，更新臨時起點currentMax = nums[i];tempStart = i;} else {// 加入之前的子數組currentMax += nums[i];}// 更新全局最大和及起止索引if (currentMax > maxSum) {maxSum = currentMax;start = tempStart;end = i;}}return new int[]{start, end, maxSum};  // 起點、終點、最大和
}

4.2 變種2：限制子數組長度（最多k個元素）

問題：找到長度不超過k的連續子數組的最大和。
思路：結合Kadane算法和前綴和優化，用滑動窗口維護前綴和的最小值（需額外處理長度限制）：

public int maxSubArrayWithLimit(int[] nums, int k) {int n = nums.length;int[] prefixSum = new int[n + 1];  // 前綴和：prefixSum[i] = sum(nums[0..i-1])for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + nums[i];}int maxSum = Integer.MIN_VALUE;// 用單調隊列維護前綴和的最小值（窗口內）Deque<Integer> deque = new ArrayDeque<>();deque.offer(0);  // 初始前綴和prefixSum[0] = 0for (int i = 1; i <= n; i++) {// 移除窗口外的前綴和（超過k個元素）while (!deque.isEmpty() && i - deque.peekFirst() > k) {deque.pollFirst();}// 當前前綴和 - 窗口內最小前綴和 = 最大子數組和maxSum = Math.max(maxSum, prefixSum[i] - prefixSum[deque.peekFirst()]);// 維護單調隊列（保證前綴和遞增）while (!deque.isEmpty() && prefixSum[i] <= prefixSum[deque.peekLast()]) {deque.pollLast();}deque.offer(i);}return maxSum;
}

4.3 變種3：允許子數組為空（返回0）

若題目允許子數組為空（即最大和可以是0，如所有元素為負數時），只需在最后對結果取max(0, maxSum)：

public int maxSubArrayAllowEmpty(int[] nums) {int currentMax = 0;  // 初始化為0（允許空數組）int maxSum = 0;for (int num : nums) {currentMax = Math.max(0, currentMax + num);  // 空數組對應0maxSum = Math.max(maxSum, currentMax);}return maxSum;
}

五、時間與空間復雜度

• 時間復雜度：$O(n)$，僅需遍歷數組一次，每次操作均為常數時間。
• 空間復雜度：$O(1)$，僅使用固定數量的變量（基礎版本），適合大規模數據。

六、實際應用場景

1. 股票收益分析：計算某段時間內連續持有股票的最大收益（將股價數組轉為每日漲跌數組）。
2. 信號處理：在噪聲信號中提取連續有效信號段（信號強度和最大的區間）。
3. 能源消耗優化：找到連續時間段內能源消耗最高的區間，用于負載均衡。
4. LeetCode經典題：LeetCode 53（最大子數組和）、LeetCode 152（乘積最大子數組，Kadane算法的變種）。

總結
Kadane算法通過動態規劃思想，以$O(n)$時間和$O(1)$空間高效解決最大子數組和問題，是算法優化的典型案例。其核心在于“局部最優選擇”——每個元素要么加入之前的子數組，要么重新開始，通過不斷更新局部最優和全局最優得到結果。
在實際應用中需注意：

• 基礎版本可直接解決無長度限制的最大子數組和問題。
• 變種問題（如限制長度、返回索引）可通過擴展算法邏輯實現。
• 結合前綴和、單調隊列等工具，可處理更復雜的場景。

That’s all, thanks for reading~~
覺得有用就點個贊、收進收藏夾吧！關注我，獲取更多干貨～