C++ Program to Find Maximum Subarray Sum

You can find the maximum subarray sum in C++ using Kadane's algorithm with int maxSubArraySum(vector& nums) that iterates through the array, tracking current and maximum sums.

Examples

Input[-2,1,-3,4,-1,2,1,-5,4]

Output6

Input[1,2,3,4,5]

Output15

Input[-1,-2,-3,-4]

Output-1

How to Think About It

To find the maximum sum of a continuous subarray, move through the array adding each number to a running total. If the running total becomes negative, reset it to zero because starting fresh might give a bigger sum. Keep track of the highest sum found during this process.

Algorithm

1

Start with two variables: current_sum = 0 and max_sum = smallest possible integer.

2

Go through each number in the array.

3

Add the current number to current_sum.

4

If current_sum is greater than max_sum, update max_sum.

5

If current_sum drops below zero, reset it to zero.

6

After checking all numbers, return max_sum.

Code

cpp

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxSubArraySum(const vector<int>& nums) {
    int max_sum = INT_MIN, current_sum = 0;
    for (int num : nums) {
        current_sum += num;
        if (current_sum > max_sum) max_sum = current_sum;
        if (current_sum < 0) current_sum = 0;
    }
    return max_sum;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << maxSubArraySum(nums) << endl;
    return 0;
}

Output

6

Dry Run

Let's trace the example array [-2, 1, -3, 4, -1, 2, 1, -5, 4] through the code.

1

Start

max_sum = -∞, current_sum = 0

2

Add -2

current_sum = 0 + (-2) = -2; max_sum = max(-∞, -2) = -2; current_sum < 0, reset to 0

3

Add 1

current_sum = 0 + 1 = 1; max_sum = max(-2, 1) = 1

4

Add -3

current_sum = 1 + (-3) = -2; max_sum = max(1, -2) = 1; current_sum < 0, reset to 0

5

Add 4

current_sum = 0 + 4 = 4; max_sum = max(1, 4) = 4

6

Add -1

current_sum = 4 + (-1) = 3; max_sum = max(4, 3) = 4

7

Add 2

current_sum = 3 + 2 = 5; max_sum = max(4, 5) = 5

8

Add 1

current_sum = 5 + 1 = 6; max_sum = max(5, 6) = 6

9

Add -5

current_sum = 6 + (-5) = 1; max_sum = max(6, 1) = 6

10

Add 4

current_sum = 1 + 4 = 5; max_sum = max(6, 5) = 6

Iteration	Current Number	Current Sum	Max Sum
1	-2	0 (reset)	-2
2	1	1	1
3	-3	0 (reset)	1
4	4	4	4
5	-1	3	4
6	2	5	5
7	1	6	6
8	-5	1	6
9	4	5	6

Why This Works

Step 1: Track current sum

We keep adding numbers to current_sum to find sums of subarrays.

Step 2: Reset when negative

If current_sum becomes negative, it can't help future sums, so reset it to zero.

Step 3: Update max sum

After each addition, update max_sum if current_sum is bigger, so we remember the best sum found.

Alternative Approaches

Brute Force

cpp

#include <iostream>
#include <vector>
using namespace std;

int maxSubArraySum(const vector<int>& nums) {
    int max_sum = nums[0];
    for (int i = 0; i < nums.size(); i++) {
        int current_sum = 0;
        for (int j = i; j < nums.size(); j++) {
            current_sum += nums[j];
            if (current_sum > max_sum) max_sum = current_sum;
        }
    }
    return max_sum;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << maxSubArraySum(nums) << endl;
    return 0;
}

This checks all subarrays but is slow (O(n²)) compared to Kadane's O(n).

Divide and Conquer

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxCrossingSum(const vector<int>& nums, int left, int mid, int right) {
    int sum = 0, left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        if (sum > left_sum) left_sum = sum;
    }
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        if (sum > right_sum) right_sum = sum;
    }
    return left_sum + right_sum;
}

int maxSubArraySumRec(const vector<int>& nums, int left, int right) {
    if (left == right) return nums[left];
    int mid = (left + right) / 2;
    int left_max = maxSubArraySumRec(nums, left, mid);
    int right_max = maxSubArraySumRec(nums, mid + 1, right);
    int cross_max = maxCrossingSum(nums, left, mid, right);
    return max({left_max, right_max, cross_max});
}

int maxSubArraySum(const vector<int>& nums) {
    return maxSubArraySumRec(nums, 0, nums.size() - 1);
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << maxSubArraySum(nums) << endl;
    return 0;
}

This uses divide and conquer with O(n log n) time, slower than Kadane but useful for teaching recursion.

Complexity: O(n) time, O(1) space

Time Complexity

Kadane's algorithm scans the array once, so it runs in linear time O(n), where n is the number of elements.

Space Complexity

It uses only a few variables, so space complexity is constant O(1).

Which Approach is Fastest?

Kadane's algorithm is fastest with O(n) time, better than brute force O(n²) and divide and conquer O(n log n).

Approach	Time	Space	Best For
Kadane's Algorithm	O(n)	O(1)	Fastest and simplest for max subarray sum
Brute Force	O(n²)	O(1)	Simple but slow, good for small arrays
Divide and Conquer	O(n log n)	O(log n)	Good for teaching recursion, slower than Kadane