Maximum Subarray — Day 16(Python)

Photo by Elena Mozhvilo on Unsplash

Today we will be looking at one of the frequently asked questions in the Amazon coding round.

Before we look into the problem, let us understand the subarray. A subarray of element-array is a contiguous block of elements from the original array.

For eg: A = [1, 2, 3, 4, 5, 6]

Some examples of subarray for array A is as follows

[1], [3, 4, 5], [6], [1, 2, 3, 4, 5, 6].

Every element in an array is an example of a subarray of the original array.

53. 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.

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 = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-2147483647]
Output: -2147483647

Constraints:

• 1 <= nums.length <= 2 * 10^4
• -231 <= nums[i] <= 231 - 1

One way to solve the given problem is by finding all the possible subarrays of the original array and find the maximum sum from the subarrays. To find subarrays, we would require two for loops that keep track of the start and end of the subarray.

class MaxSumFinder:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = float('-inf')
        for start in range(len(nums)):
            for end in range(start, len(nums)):
                if max_sum <= sum(nums[start:end+1]):
                    max_sum = sum(nums[start:end+1])
        return max_sum

Complexity Analysis

Time Complexity

Here we are nesting two loops. The outer for-loop runs for N times where N is the length of the array, while the inner for-loop runs for N-1. Therefore the time complexity is O(N*(N-1)) i.e. O(N²).

Space Complexity

Since we are not using any extra space for the above algorithm the space complexity is O(1).

Can we try improving the time complexity? O(N²) would take a lot of time if we have 2*10⁴ elements in our array.

One way is by using Kadane’s Algorithm.

We try finding the local maxima that help us in finding out the global maxima. Each time we encounter a new element in the array see if including it helps in improving the sum of the subarray. If not, the new subarray will start at the current index.

Initialize the first element in our array as our local maxima and global maxima. Run a loop through all the elements of the array, check if adding the current element to the subarray improves the local maxima or if the current element is higher than the addition. Since we want a subarray, either you add the current number to the earlier subarray or you start the subarray from the current element. To find the global maxima compare previous global maxima to new local maxima.

class MaxSumFinder:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        current_sum = max_sum
        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum+nums[i])
            max_sum = max(current_sum, max_sum)
        return max_sum

Complexity Analysis

Time Complexity

Here we are using one loop to traverse through all the elements of the array hence time complexity is O(N).

Space Complexity

Since we are not using any extra space for the above algorithm the space complexity is O(1).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.