Maximum Subarray — LeetCode 53 Python Solution
MediumArrayDivide and ConquerDynamic Programming
- Problem
- #53
- Pattern
- Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example
- Input
- nums = [-2,1,-3,4,-1,2,1,-5,4]
- Output
- 6
- Explanation
- The subarray [4,-1,2,1] has the largest sum 6.
Python solution
Python
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = f = nums[0]
for x in nums[1:]:
f = max(f, 0) + x
ans = max(ans, f)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the array \textit{nums} |
| Space | O(1) auxiliary |
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 53. Maximum Subarray is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
On study lists
This problem is on Blind 75, NeetCode 150, Grind 75 and Top Interview 150.
Frequently asked questions
- How hard is LeetCode 53. Maximum Subarray?
- LeetCode 53. Maximum Subarray is rated Medium on LeetCode.
- What is the time complexity of LeetCode 53. Maximum Subarray?
- The Python solution on this page runs in O(n), where n is the length of the array \textit{nums}.
- What is the space complexity of LeetCode 53. Maximum Subarray?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 53. Maximum Subarray cover?
- LeetCode 53. Maximum Subarray is tagged Array, Divide and Conquer and Dynamic Programming on LeetCode.