To solve this problem, we need to find the contiguous subarray within an array (containing at least one number) that has the largest sum. This is a classic problem that can be efficiently solved using Kadane's algorithm, which runs in O(n) time complexity and uses O(1) additional space.
Approach: Kadane's Algorithm
The key idea of Kadane's algorithm is to keep track of two values as we iterate through the array:
- Current Maximum: The maximum sum of the subarray ending at the current position. This value decides whether to start a new subarray at the current element or continue the previous subarray.
- Global Maximum: The maximum sum of any subarray found so far.
Steps:
- Initialize both
current_maxandglobal_maxwith the first element of the array. - For each subsequent element:
- Update
current_maxto be the maximum of the current element itself or the sum ofcurrent_maxand the current element. This step decides whether to start a new subarray at the current element or extend the previous one. - If
current_maxexceedsglobal_max, updateglobal_maxtocurrent_max.
- Update
- Return
global_maxas the result.
Solution Code
class Solution:
# @param A, a list of integers
# @return an integer
def maxSubArray(self, A):
current_max = global_max = A[0]
for num in A[1:]:
current_max = max(num, current_max + num)
if current_max > global_max:
global_max = current_max
return global_max
Explanation
- Initialization: We start with
current_maxandglobal_maxset to the first element because the subarray must contain at least one element. - Iteration: For each element, we check if starting a new subarray at the current element gives a better sum than continuing the previous subarray. This is done by comparing the current element with the sum of the current element and the previous
current_max. - Update Global Maximum: Whenever the
current_max(sum of the subarray ending at the current position) is larger than theglobal_max, we update theglobal_maxto this value.
This approach efficiently finds the maximum subarray sum with optimal time and space complexity, handling all edge cases (including all negative elements) correctly. For example, if all elements are negative, the algorithm returns the least negative element (since it's the maximum possible subarray sum in that case).
Example: For the array [-2,1,-3,4,-1,2,1,-5,4], the maximum subarray sum is 6 (from the subarray [4,-1,2,1]), which the algorithm correctly identifies.
This solution is optimal and widely used for this problem. It ensures we traverse the array only once, making it very efficient even for large input sizes.
作者声明:本文包含人工智能生成内容。