Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 53 with 15 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 53 # by problem number
lcpy gen -s maximum_subarray # by problem name
nums, find the subarray with the largest sum, and return its sum.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Input: nums = [1]
Output: 1
Input: nums = [5,4,-1,7,8]
Output: 23
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
class Solution:
# Time: O(n)
# Space: O(1)
def max_sub_array(self, nums: list[int]) -> int:
max_sum = current_sum = nums[0]
for i in range(1, len(nums)):
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum)
return max_sum
| Time | Space |
|---|---|
| O(n) | O(1) |