LC 53 - Maximum Subarray
Question
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example 1:
1
2
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:
1
2
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
1
2
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 <= 105-104 <= nums[i] <= 104
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.
Links
Question here and solution here
Solution
concept
The algorithm to be used is called Kadane’s algorithm. The basic idea is that since the array contains negative values and any prefix that is negative does not contribute meaningfully to a bigger sum so we should start our “window” fresh. So we have to keep checking if the current sum is positive or negative, if negative we should start our subarray fresh.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
"""
Kadane's algo
"""
def maxSubArray(self, nums: List[int]) -> int:
max_sum = nums[0]
cur_sum = 0
for n in nums:
if cur_sum < 0: # start fresh if the prefix sum of this num is negative
cur_sum = 0
cur_sum += n
max_sum = max(max_sum, cur_sum)
return max_sum
class Solution:
"""
Kadane's algo
different form
"""
def maxSubArray(self, nums: List[int]) -> int:
max_sum = max(nums)
cur_sum = 0
for n in nums:
cur_sum = max(n, cur_sum + n)
max_sum = max(max_sum, cur_sum)
return ans
Complexity
time: $O(n)$
space: $O(1)$