[LeetCode] 0053. Maximum Subarray

/ Leetcode, Technical Article / By
maximum-subarray

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

Table of contents

Medium

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

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.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

  • 1 <= nums.length <= 10 5
  • -10 4 <= nums[i] <= 10 4

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Python

				
					class Solution: def maxSubArray(self, nums: List[int]) -> int: maxNum = -100000 sum = 0 for i in range(len(nums)): sum += nums[i] if sum < nums[i ]: sum = nums[i] maxNum = max(sum, maxNum) return maxNum

related articles