Find the maximum subarray sum

DevSniper
Published : 21 July 2024

202 Views

Array Divide and Conquer Coding Problems DSA

Given an integer array arr of size N that contains positive and negative numbers. Your task is to find the maximum subarray sum

Example 1 :-

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

Output : 10

arr : [-2,1,3,4,-1,2,1,-5,4] then the maximum subarray sum is 10 (see highlighted elements)

Example 2 :-

[10,6,-1,2,8]

Output : 25

arr : [10,6,-1,2,8 ] then the maximum subarray sum is 25 (see highlighted elements)

Constraints :

N = arr.length
1 <= arr.length <= 10^5
-10^4 <= nums[i] <= 10^4

Approach 1 : Brute Force Approach Using Nested Loop

Brute Force approach involves using nested loops. The outer loop selects the starting element, while the inner loop calculates the maximum possible sum from starting element. It compares each local maximum with the overall maximum sum if local sum if greater than overall maximum sum then update overall maximum sum with local sum. At the end of both loop overall maximum sum contains maximum subarray sum.

C++

Java

#include <bits/stdc++.h>
using namespace std;

int FindMaxSubArraySum(int arr[], int n)
{
    int maxSum=arr[0];
    for(int i=0; i<n; i++) {
        int localSum=arr[i];
        for(int j=i+1; j<n; j++) {
            maxSum = max(maxSum, localSum);
            localSum+=arr[j];
        }
        maxSum = max(maxSum, localSum);
    }
    return maxSum;
}
int main()
{
    int arr[] = {10, -6, 1, 2, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << FindMaxSubArraySum(arr,n) <<endl;
}

Time Complexity : O(N^2)

Space Complexity : O(1)

Approach 2 : Using Divide and Conquer Algorithm

Brute Force algorithm time complexity is O(N^2) . We can reduce this time complexity to O(NlogN) by using Divide and Conquer approach.

Steps of Divide and Conquer Algorithm

Divide the array into two equal parts.
Find the maximum subarray sum in each parts.
Recursively find the maximum subarray sum of the left half part.
Recursively find the maximum subarray sum of the right half part.
Find the maximum sum of the subarray that includes elements from both halves.
The maximum subarray sum will be the maximum of left half, right half and the sum that includes elements from both halves.

C++

Java

#include <bits/stdc++.h>
using namespace std;

int maxCrossingSum(int arr[], int l, int m, int h)
{
    int sum = 0;
    int leftSum = INT_MIN;
    for (int i = m; i >= l; i--) {
        sum = sum + arr[i];
        if (sum > leftSum) {
            leftSum = sum;
        }
    }
    sum = 0;
    int rightSum = INT_MIN;
    for (int i = m; i <= h; i++) {
        sum = sum + arr[i];
        if (sum > rightSum) {
            rightSum = sum;
        }

    }
    return max(max(leftSum, rightSum),leftSum + rightSum - arr[m]);
}

int FindMaxSubArraySum(int arr[], int l,int h)
{
    if (l > h)
        return INT_MIN;
    if (l == h)
        return arr[l];
    int mid = (l + h) / 2;
    return max(max(FindMaxSubArraySum(arr, l, mid - 1),
                   FindMaxSubArraySum(arr, mid + 1, h)),
               maxCrossingSum(arr, l, mid, h));
}
int main()
{
    int arr[] = {10, -6, 1, 2, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << FindMaxSubArraySum(arr,0,n-1) <<endl;
}

Time Complexity : FindmaxSubArraySum() is a recursive method and its time complexity can be described using the following recurrence relation :- 2T(n/2) + ?(n) => O(NlogN)

Space Complexity : The recursion stack requires O(logn) space due to the recursive calls so Space Complexity will be => O(lonN)

Approach 3 : Using Kadane’s Algorithm

Kadane’s Algorithm is used to find the maximum subarray sum of an array of numbers efficiently in O(N) time complexity.

Kadane's algorithm works by maintaining two variables (current_max_sum and max_sum). current_max_sum which tracks the maximum sum of a contiguous subarray ending at the current index and max_sum which stores the overall maximum sum found so far. During each iteration if current_max_sum exceeds max_sum update max_sum with current_max_sum . By the end of the iteration max_sum represents the maximum subarray sum of the array.

Steps :

Initialize max_sum with a very small number (or negative infinity) to handle cases where all array elements are negative.
Initialize current_max_sum to 0 to keep track of the sum of the current subarray.
Iterate over array
1. Update current_max_sum to be either the current element itself (starting a new subarray) or the sum of current_max_sum and the current element (extending the current subarray).
2. Update max_sum to be the maximum of max_sum and current_max_sum.
max_sum will hold the maximum subarray sum of the array.

C++

Java

Python

#include <bits/stdc++.h>
using namespace std;

int FindMaxSubArraySum(int arr[],int n)
{
    int max_sum = INT_MIN;
    int current_max_sum = 0;
    for(int i=0; i<n; i++) {
        current_max_sum=max(arr[i],current_max_sum+arr[i]);
        max_sum= max(max_sum,current_max_sum);
    }
    return max_sum;
}
int main()
{
    int arr[] = {-10, 6, -1, 3, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << FindMaxSubArraySum(arr,n) <<endl;
}

Time Complexity : O(N)

Space Complexity : O(1)