MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Maximum Subarray

Written By

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