Maximum Subarray

Find the contiguous subarray with the largest sum

問題描述

給你一個整數數組 nums，請找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

範例

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子數組 [4,-1,2,1] 的和最大，為 6

輸入：nums = [1]
輸出：1

輸入：nums = [5,4,-1,7,8]
輸出：23

限制條件

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

解題思路

狀態定義

定義 currentSum 為以當前元素結尾的最大子數組和

狀態轉移

對於每個元素，選擇：開始新的子數組 OR 延續之前的子數組

記錄最大值

在遍歷過程中記錄所有可能的最大和

解決方案

export function maxSubArray(nums: number[]): number {
  let [maxSum, currentSum] = [nums[0], nums[0]];

  nums.forEach((num, index) => {
    if (index === 0)
      return;

    // 選擇開始新的子數組或延續當前子數組
    currentSum = Math.max(num, currentSum + num);
    // 更新全局最大和
    maxSum = Math.max(maxSum, currentSum);
  });

  return maxSum;
}

import { describe, expect, it } from 'vitest';
import { maxSubArray } from './solution';

describe('53. Maximum Subarray', () => {
  it('should find the maximum subarray sum', () => {
    expect(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])).toBe(6);
  });

  it('should handle all negative numbers', () => {
    expect(maxSubArray([-1, -2, -3, -4])).toBe(-1);
  });

  it('should handle single element', () => {
    expect(maxSubArray([1])).toBe(1);
  });

  it('should handle all positive numbers', () => {
    expect(maxSubArray([1, 2, 3, 4])).toBe(10);
  });
});

Kadane 算法詳解

這是動態規劃中的經典算法，由 Joseph Kadane 提出，專門解決最大子數組和問題。

核心思想

在每個位置，我們都面臨一個選擇：

開始新的子數組：只包含當前元素
延續之前的子數組：將當前元素加入之前的和

選擇標準：Math.max(num, currentSum + num)

算法步驟

初始化：
- maxSum = 第一個元素（全局最大和）
- currentSum = 第一個元素（當前子數組和）
遍歷數組：
- 更新當前子數組和
- 更新全局最大和

狀態轉移方程：

currentSum = max(nums[i], currentSum + nums[i])
maxSum = max(maxSum, currentSum)

複雜度分析

時間複雜度: O(n) - 只需遍歷數組一次
空間複雜度: O(1) - 只使用常數額外空間

這是動態規劃空間優化的典型例子：我們不需要保存所有的歷史狀態，只需要記住前一個狀態即可

算法執行過程

以 nums = [-2,1,-3,4,-1,2,1,-5,4] 為例：

i	nums[i]	currentSum	maxSum	說明
0	-2	-2	-2	初始化
1	1	1	1	max(1, -2+1) = 1
2	-3	-2	1	max(-3, 1-3) = -2
3	4	4	4	max(4, -2+4) = 4
4	-1	3	4	max(-1, 4-1) = 3
5	2	5	5	max(2, 3+2) = 5
6	1	6	6	max(1, 5+1) = 6
7	-5	1	6	max(-5, 6-5) = 1
8	4	5	6	max(4, 1+4) = 5

最大子數組：[4,-1,2,1]，和為 6

邊界情況處理

全為負數：返回最大的負數
單個元素：返回該元素
全為正數：返回所有元素的和

變體問題

返回最大子數組的起始和結束位置
找出所有最大子數組
環形數組的最大子數組
最大子數組乘積

分治法解法 (進階)

function maxSubArrayDivide(nums: number[]): number {
  function divideAndConquer(left: number, right: number): number {
    if (left === right) return nums[left];
    
    const mid = Math.floor((left + right) / 2);
    const leftMax = divideAndConquer(left, mid);
    const rightMax = divideAndConquer(mid + 1, right);
    
    // 跨越中點的最大子數組
    let leftSum = -Infinity, sum = 0;
    for (let i = mid; i >= left; i--) {
      sum += nums[i];
      leftSum = Math.max(leftSum, sum);
    }
    
    let rightSum = -Infinity; sum = 0;
    for (let i = mid + 1; i <= right; i++) {
      sum += nums[i];
      rightSum = Math.max(rightSum, sum);
    }
    
    return Math.max(leftMax, rightMax, leftSum + rightSum);
  }
  
  return divideAndConquer(0, nums.length - 1);
}

時間複雜度：O(n log n)，空間複雜度：O(log n)