寻找最大和子数组

Problem

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

Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum, which is 6.

Example 2: Input: nums = [1] Output: 1

Example 3: Input: nums = [5,4,-1,7,8] Output: 23

Idea

Use Kadane’s Algorithm. Scan the array from left to right while keeping the best subarray sum that ends at the current position.

For each number, decide whether to: - extend the previous subarray, or - start a new subarray from the current number.

Keep another variable for the largest sum seen so far. If the previous running sum becomes harmful, starting fresh from the current number gives a better result.

Time complexity: O(n), Space complexity: O(1)

Pseudo-code

currentSum = nums[0];
maxSum = nums[0];

for each remaining value in nums {
    currentSum = max(value, currentSum + value);
    maxSum = max(maxSum, currentSum);
}

return maxSum;