aloalgoMaximum Subarray Sum
Medium
You are given an integer array named nums.
Your task is to find the contiguous subarray within nums that has the largest possible sum.
Remember that:
- A subarray is a continuous segment of the original array.
- A subarray must contain at least one number.
Return the largest sum found.
Example 1
Input
[1]
Output
1
Explanation:
The subarray [1] has the largest sum = 1.
Example 2
Input
[4, -1, 2, 1, -5, 4]
Output
6
Explanation:
The subarray [4, -1, 2, 1] has the largest sum of 6.
Example 3
Input
[5, -1, 4, -2, 6]
Output
12
Explanation:
Although there are negative numbers, the entire array [5, -1, 4, -2, 6] forms the maximum subarray with a sum of 12.
Input
[1]
Output
1