Kadane's Algorithm
Maximum Subarray
Screen Recording 2021-11-01 at 15.30.10.mov
"""
Maximum Subarray:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
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
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
https://leetcode.com/problems/maximum-subarray/
"""
from typing import List
# O(n) time | O(1) space
class Solution:
def maxSubArray(self, nums: List[int]):
# # # find the maximum subarray per given element:
# # ***check which one is larger:***
# # ***adding the element to the current subarray or starting a new subarray at the element***
# the max subarray we found's sum
max_sa_sum = float("-inf")
# sum of the current subarray that we are working with
curr_subarray = float("-inf")
for num in nums:
# check if adding the num to the current subarray will be
# a longer sum than starting a new subarray at the element
# then the current subarray should be the longer/larger of the two
curr_subarray = max(num, curr_subarray + num)
# record the largest (sum) we found
max_sa_sum = max(curr_subarray, max_sa_sum)
return max_sa_sum
"""
Inputs:
[-2,1,-3,4,-1,2,1,-5,4]
[-2]
[1]
[-2,-3,-1,-5]
[1,2,3,4,5,6,7,8,9,0]
Outputs:
6
-2
1
-1
45
"""
Find the original version of this page (with additional content) on Notion here.
Last update:
December 13, 2021 16:05:48
Created: December 13, 2021 16:05:48
Created: December 13, 2021 16:05:48
Authors: