LeetCode | Maximum Subarray | Amazon Interview Questions | Geek Hacker

Problem Statement

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.

Constraints

• 1 <= nums.length <= 3 * 10^4
• -10^5 <= nums[i] <= 10^5

Examples

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

Analysis

Source: geeksforgeeks.org

Before attempting to solve the Maximum Subarray problem, let’s analyze some of this problem properties:

1. If the array contains all non-negative numbers, then the problem is trivial; a maximum subarray is the entire array.
2. If the array contains all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array.
3. Several different sub-arrays may have the same maximum sum.

This problem can be solved using different algorithms including Kadane’s algorithm.

Kadane’s Algorithm

Kadane’s algorithm looks for all positive contiguous segments of the array max_ending_here. And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive-sum compare it with max_so_far and update max_so_far if it is greater than max_so_far.

Algorithm

1. Initiate max_so_far to the smallest negative integer.
2. Initiate max_ending_here to 0.
3. Traverse nums.
4. Add the current array element to max_ending_here , then compare it to max_so_far .
5. Compare max_ending_here to 0

Python 3 Code

from sys import maxint
class Solution(object):
    def maxSubArray(self, nums):
        max_so_far = -maxint - 1
        max_ending_here = 0
      
        for n in nums:
            max_ending_here = max_ending_here + n
            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

Complexity

Time Complexity

O(n)

Space Complexity

O(1)

For more LeetCode problems’ solutions, visit my GitHub repo.

If you enjoyed reading this article, please recommend and share it to help others find it!