53. Maximum Subarray

Array, Divide and Conquer, DP, AMateList · 03 Sep 2023

Problem Statement

link: https://leetcode.com/problems/maximum-subarray/ https://leetcode.cn/problems/maximum-subarray/

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

Input: nums = [1] Output: 1

Input: nums = [5,4,-1,7,8] Output: 23

Solution Approach

The solution utilizes Kadane’s algorithm to efficiently determine the maximum sum of a contiguous subarray.

Algorithm

Initialization: Begin with the first element as both the current sum (cur) and the maximum sum (res).
Iterative Update: For each element, adjust the cur by deciding whether to include the element in the existing subarray or start a new subarray from the current element.
Result Determination: Continuously compare and update the res with cur to keep track of the maximum subarray sum, and return res after processing all elements.

Implement

    class Solution:
      def maxSubArray(self, nums: List[int]) -> int:
          n = len(nums)
          cur = res = nums[0]
          for i in range(1, n):
              cur = max(cur + nums[i], nums[i])
              res = max(cur, res)
          return res