Maximum Subarray Sum

Maximum Subarray Sum

This is a classic and very famous problem in programming. Once you understand it, you will start seeing the same idea in many other problems. Let's learn it step by step.

What is a subarray?

First, we need one simple idea: a subarray.

A subarray is a piece of an array that you take continuously, without skipping any element. You pick a starting point and an ending point, and you keep everything in between.

For example, if the array is:

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

then some valid subarrays are:

• [1, -3, 4] (these sit next to each other)
• [4, -1, 2, 1]
• [-2] (a single element is also a subarray)

But [1, 4, 2] is not a subarray, because in the original array those numbers are not next to each other. You jumped over some elements, and that is not allowed.

Also remember: the problem says non-empty, so the subarray must have at least one number in it.

The actual task

We are given an array of integers. Some are positive, some are negative. Among all possible subarrays, we must find the one whose numbers add up to the largest total, and return that total (the sum, not the subarray itself).

Walking through Example 1

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

The answer here is 6.

Why? Look at the subarray [4, -1, 2, 1]. Let's add it up:

4 + (-1) + 2 + 1 = 6

No other continuous piece of this array can beat 6. Notice something interesting: this winning subarray even includes a negative number, -1. We kept it because the numbers around it are strong enough that holding on to -1 still leads to a bigger total. That is the tricky part of this problem — sometimes you carry a small loss to reach a bigger gain.

Walking through Example 2

arr = [5, 4, -1, 7, 8]

The answer is 23.

Here the best choice is to take the whole array:

5 + 4 + (-1) + 7 + 8 = 23

When the positive numbers are large and the negatives are small, often the best subarray is the entire array.

A simple way to think about it

Imagine you are walking through the array from left to right, keeping a "running total" of the numbers you have collected so far.

• If your running total is still positive, it is helping you — keep going and add the next number.
• But if your running total ever drops below zero, it has become a burden. Carrying a negative total into the future only drags down whatever comes next. So you drop it and start fresh from the next number.

All the while, you remember the best total you have ever seen. At the end, that best total is your answer.

This idea — extend when it helps, restart when it hurts, and always remember the best — is the heart of the famous solution to this problem (known as Kadane's algorithm). Your job is to fill in the function:

int maxSubarraySum(vector<int> &arr) {

}

You take in the array arr and return a single integer: the maximum subarray sum.