This content originally appeared on DEV Community and was authored by DEV Community
Instructions
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Approach
We can initialize maximum sum at index 0 and update it as we iterate through the array when we find a new maximum.
We also initialize a current sum at index 0 and update it by adding num at current index. We also compare if current sum is greater than num at current index and update it. We then compare if the current sum is greater than maximum sum and update maximum sum.
Python Implementation
def maxSubArray(nums):
if not nums:
return 0
currSum = maxSum = nums[0]
for i in range(1,len(nums)):
currSum += nums[i]
currSum = max(currSum, nums[i])
maxSum = max(maxSum, currSum)
return maxSum
The space complexity is O(1) because we do not use an extra memory and the time complexity is O(n) because we have to go through each element in the array.
Kadane's Algorithm
We can also implement Kadane's algorithm to achieve O(n) time complexity.
We can keep track of maximum sum contiguous segment encountered so far and update it when we get a new max.
Python Implementation
def kadane(a):
size = len(a)
max_so_far = -float('inf')
max_ending_here = 0
for i in range(0, size):
max_ending_here = max_ending_here + a[i]
if (max_so_far < max_ending_here):
max_so_far = max_ending_here
if max_ending_here < 0:
max_ending_here = 0
return max_so_far
Let's go through the code.
We initialize max_so_far as negative infinity to keep track of the max seen so far and max_ending_here at 0. Then we iterate through the arr and update the two variables through comparisons.
Finally we return the maximum sum.
This content originally appeared on DEV Community and was authored by DEV Community
DEV Community | Sciencx (2022-02-25T17:41:15+00:00) Maximum Subarray Sum. Retrieved from https://www.scien.cx/2022/02/25/maximum-subarray-sum/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.