How to Solve Maximum Subarray

Written By
Adam Bhula

Maximum Subarray Introduction

The Maximum Subarray problem asks us to find the subarray with the largest sum of a given array. This problem can be solved using dynamic programming and more specifically Kadane's Algorithm.

Maximum Subarray Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example Inputs and Outputs

Example 1

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

Example 2

Input: nums = [1]
Output: 1

Example 3

Input: nums = [5, 4, -1, 7, 8]
Output: 23

Maximum Subarray Solutions

To solve this problem, we can use a technique called Kadane's algorithm. Here's how it works:

Imagine you're walking through the given array from left to right, keeping track of the sum of the subarray you've encountered so far. At each step, you have two options: you can either extend the current subarray by including the current element, or you can start a new subarray from the current element. The idea is to choose the option that gives you the maximum sum.

To do this, you maintain two variables: one to track the current sum and another to store the maximum sum found so far. As you move forward in the array, you update the current sum by adding the current element or starting afresh. Whenever the current sum becomes larger than the maximum sum, you update the maximum sum. By the end of the traversal, the maximum sum will represent the sum of the subarray with the largest sum.

This approach handles different cases like arrays with negative numbers or arrays with only one element. It considers both individual elements and subarrays to find the subarray with the largest sum. The key idea is to dynamically update the current sum and compare it with the maximum sum as you progress through the array. By doing this, we can efficiently find the solution in a single pass through the array.

def maxSubArray(nums):
    maxSum = nums[0]  # Initialize maxSum with the first element of the array
    currentSum = nums[0]  # Initialize currentSum with the first element of the array

    for i in range(1, len(nums)):
        currentSum = max(nums[i], currentSum + nums[i])
        maxSum = max(maxSum, currentSum)

    return maxSum

# Test case 1
nums1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result1 = maxSubArray(nums1)
print("Maximum subarray sum for nums1:", result1)  # Expected output: 6

# Test case 2
nums2 = [1]
result2 = maxSubArray(nums2)
print("Maximum subarray sum for nums2:", result2)  # Expected output: 1

# Test case 3
nums3 = [5, 4, -1, 7, 8]
result3 = maxSubArray(nums3)
print("Maximum subarray sum for nums3:", result3)  # Expected output: 23

Time/Space Complexity Analysis

  • Time Complexity: O(N), where N is the length of the input array nums. This is because we iterate through each element of the array once.
  • Space Complexity: O(1), as we use a constant amount of extra space to store the current sum and maximum sum.

About is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.