Maximum Subarray
•--
Find the contiguous subarray with maximum sum using Kadane's algorithm
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 延續之前的子數組
### 記錄最大值 在遍歷過程中記錄所有可能的最大和
解決方案
typescript
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;
}