Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C++

Solution: Maximum Subarray

Explore the maximum subarray problem by learning how to apply Kadane's algorithm with a dynamic programming approach. Understand how to iterate through an array to find the contiguous subarray with the highest sum efficiently. This lesson guides you through the implementation details and complexity analysis, helping you master a common coding interview challenge.

We'll cover the following...

Statement

Given an unsorted array nums, find the sum of the maximum sum subarray. The maximum sum subarray is an array of contiguous elements in nums for which the sum of the elements is maximum.

Constraints:

  • 1≤1 \leq nums.length ≤103\leq 10^3

  • −104≤-10^4 \leq nums[i] ≤104\leq 10^4

Solution

The maximum subarray sum problem inherently involves examining various subarrays to check if their sum is maximized, and the most convenient and efficient way to do this is using dynamic programming. The key idea is to efficiently find the maximum subarray ending at any position based on the maximum subarray ending at the previous position.

In the context of this problem, we’ll use Kadane’s algorithm. It uses the bottom-up approach of dynamic programming to solve subproblems iteratively, starting from the smallest subproblems and building up toward the larger problem. The subproblem here is to find the maximum subarray sum that ends at a specific index i. We need to calculate this for every index i in the array. The base case is the first element of the array, where both the current subarray sum and maximum subarray sum are initialized with the first element’s value. This is the starting point for solving the subproblems. We reuse the previously computed maximum subarray sum at each step to find the solution for the current subproblem.

The steps of the algorithm are given below:

  • Initialize a currMax variable to keep track of the maximum sum of the current array index and another globalMax variable to keep track of the largest sum seen so far. Both variables will be initialized with the first element of nums.

  • Traverse the array from the second element until the end of the array is reached.

  • While traversing, if currMax is less than 0, assign it the element at the current index. Otherwise, add the element at the current index to currMax.

  • Next, if globalMax is less than currMax, reassign it to currMax.

Let’s look at the illustration below to better understand the solution:

canvasAnimation-image
1 / 10

Let's look at the code for this solution below:

C++
#include <iostream>
#include <string>
using namespace std;
int maxSumArr(int nums[], int arrSize) {
    if (arrSize < 1) {
        return 0;
    }
    int currMax = nums[0];
    int globalMax = nums[0];
    for (int i = 1; i < arrSize; i++) {
        if (currMax < 0) {
            currMax = nums[i];
        } else {
            currMax += nums[i];
        }
        if (globalMax < currMax) {
            globalMax = currMax;
        }
    }
    return globalMax;
}
int main() {
    int inputs[][10] = {
        {1, 2, 2, 3, 3, 1, 4},
        {2, 2, 1},
        {4, 1, 2, 1, 2},
        {-4, -1, -2, -1, -2},
        {-4, 2, -5, 1, 2, 3, 6, -5, 1}, 
        {25}
    };
    int sizes[] = {7, 3, 5, 5, 9, 1};
    for (int i = 0; i < sizeof(inputs) / sizeof(inputs[0]); i++) {
        cout << i + 1 << ".\tArray: [";
        for (int j = 0; j < sizes[i]; j++) {
            cout << inputs[i][j];
            if (j != sizes[i] - 1) {
                cout << ", ";
            }
        }
        cout << "]" << endl;
        cout << "\tMaximum Sum: " << maxSumArr(inputs[i], sizes[i]) << endl;
        cout << "-" << string(75, '-') << endl;
    }
    return 0;
}

Complexity analysis

Let's look at the time and space complexity of this solution:

Time complexity

The time complexity of this solution is O(n)O(n), because we iterate the input array once.

Space complexity

The space complexity of this solution is O(1)O(1), because no extra space is used.