Maximum Subarray Problem: Brute‑Force, Divide‑and‑Conquer, and Dynamic‑Programming Solutions in C++

Today we discuss the classic "Maximum Subarray" problem: given an integer array, find a contiguous sub‑array whose sum is maximal.

Brute Force

The simplest approach enumerates every possible sub‑array and computes its sum, selecting the largest. For an array of length n this requires O(n³) time.

int sum(vector<int>& nums, int b, int e){
    int res = 0;
    for(; b <= e; b++) {
        res += nums[b];
    }
    return res;
}
int maxSubArray(vector<int>& nums) {
    int size = nums.size();
    int res = 0x80000000;
    for(int i = 0; i < size; i++) {
        for(int j = i; j < size; j++) {
            res = max(res, sum(nums, i, j));
        }
    }
    return res;
}

This solution runs in O(n³) time because generating all sub‑arrays costs O(n²) and each sum calculation costs O(n).

Improved O(n²) Approach

By reusing the sum of the previous sub‑array we avoid recomputing from scratch, reducing the overall complexity to O(n²).

int maxSubArray(vector<int>& nums) {
    int size = nums.size();
    int res = 0x80000000;
    for(int i = 0; i < size; i++) {
        int sumer = nums[i];
        res = max(res, sumer);
        for(int j = i + 1; j < size; j++) {
            sumer += nums[j];
            res = max(res, sumer);
        }
    }
    return res;
}

The time complexity drops to O(n²).

Divide and Conquer

The array is recursively split into halves; the maximum sub‑array can lie entirely in the left half, the right half, or cross the middle. Combining the three cases yields an O(N log N) solution.

int getMaxSum(vector<int>& nums, int b, int e) {
    if(b == e) return nums[b];
    if(b == e - 1) return max(nums[b], max(nums[e], nums[b]+nums[e]));
    int m = (b + e) / 2;
    int maxleft = nums[m];
    int maxright = nums[m];
    int sum = nums[m];
    for(int i = m + 1; i <= e; i++) {
        sum += nums[i];
        maxright = max(maxright, sum);
    }
    sum = nums[m];
    for(int i = m - 1; i >= b; i--) {
        sum += nums[i];
        maxleft = max(maxleft, sum);
    }
    return max(getMaxSum(nums, b, m - 1), max(getMaxSum(nums, m + 1, e), maxleft+maxright-nums[m]));
}
int maxSubArray(vector<int>& nums) {
    return getMaxSum(nums, 0, nums.size()-1);
}

This method achieves O(N log N) time.

Dynamic Programming

Define dp(i) as the maximum sub‑array sum ending at index i. The recurrence dp(i) = max(dp(i‑1) + A[i], A[i]) leads to a linear‑time solution.

int maxSubArray(vector<int>& nums) {
    int size = nums.size();
    vector<int> dp(size, 0);
    int res = dp[0] = nums[0];
    for(int i = 1; i < size; i++) {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        res = max(res, dp[i]);
    }
    return res;
}

The algorithm runs in O(N) time and uses only O(1) extra space if the dp array is omitted.