Maximum Sum Subarray - C++ Solution

1. Introduction

In this post, we explore a classic problem in array processing and dynamic programming: the Maximum Sum Subarray problem. This problem is a foundational concept in algorithm design and has applications in various domains including finance and signal processing.

Problem

Given an integer array, our objective is to find the subarray that has the maximum sum among all possible subarrays. A subarray is a contiguous part of the array.

2. Solution Steps

1. Initialize two variables, currentSum, and maxSum, to track the sum of the current subarray and the maximum sum found so far.

2. Iterate through the array, adding each element to currentSum.

3. If currentSum becomes negative, reset it to zero. This step ensures we only consider subarrays with positive sums.

4. Update maxSum if currentSum is greater than maxSum.

5. Continue this process until the end of the array.

6. The maxSum at the end of the iteration is the maximum sum of any subarray.

3. Code Program

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

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

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

Output:

Maximum Sum Subarray: 6

Explanation:

In the provided examples:

- For [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum sum subarray is [4, -1, 2, 1] with a sum of 6.

- For [-7, -3, -2, -4], the maximum sum is -2, which is the largest number in the array.

- For [-2, 2, -1, 2, 1, 6, -10, 6, 4, -8], multiple subarrays tie for the maximum sum of 10, such as [2, -1, 2, 1, 6], [6, 4], and [2, -1, 2, 1, 6, -10, 6, 4].