DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 967,611 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Bernice Waweru
Bernice Waweru

Posted on • Updated on

Maximum Subarray Sum

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
Enter fullscreen mode Exit fullscreen mode

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.

Oldest comments (0)

DEV has this feature:

Settings

Go to your customization settings to nudge your home feed to show content more relevant to your developer experience level. πŸ›