Maximum Subarray

Given an array of integers nums, find the contiguous subarray that has the largest sum and return that sum. A subarray is any non-empty sequence of adjacent…

Given an array of integers `nums`, find the contiguous subarray that has the largest sum and return that sum. A subarray is any non-empty sequence of adjacent elements from the original array. The array may contain both positive and negative integers.

- `1 <= nums.length <= 10^5` - `-10^4 <= nums[i] <= 10^4` - The interactive visualizer accepts at most 12 values; longer valid arrays are execution-only.

Example 1: input nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]; output 6. The subarray [4, -1, 2, 1] has the largest sum, 6.

Example 2: input nums = [-8, -3, -6, -2, -5, -4]; output -2. Every element is negative, so the single-element subarray [-2] gives the maximum sum of -2.

Example 3: input nums = [1, 2, 3, 4, 5]; output 15. All elements are positive, so the entire array is the maximum subarray: 1 + 2 + 3 + 4 + 5 = 15.

Category: Arrays. Topic: arrays. Difficulty: Medium. Patterns: dynamic-programming, divide-and-conquer.