Problem Statement

Given an array of integers, the task is to find the contiguous subarray with the largest sum.

A subarray is a contiguous non-empty sequence of elements within an array.

LeetCode:

• https://leetcode.com/problems/maximum-subarray/description/

Examples

Example 1:

Input: arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}

Output: The largest sum of 6
{4, -1, 2, 1}

Example 2:

Input: nums = [-2, -3, -7, -2, -10, -4]
Output: -2

Explanation: The element on index 0 or index 3 make up the largest sum when taken as a subarray.

Different Approaches

1️⃣ Brute Force Approach (TLE)

The brute force approach involves checking every possible subarray and calculating its sum. We iterate through the array and for each starting index, we calculate the sum of all possible subarrays starting from that index. Finally, we return the maximum sum found.

Code:

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

int maxSubarraySum(int arr[], int n) {
    int maxi = INT_MIN; // maximum sum

    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // subarray = arr[i.....j]
            int sum = 0;

            //add all the elements of subarray:
            for (int k = i; k <= j; k++) {
                sum += arr[k];
            }

            maxi = max(maxi, sum);
        }
    }

    return maxi;
}

int main()
{
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxSum = maxSubarraySum(arr, n);
    cout << "The maximum subarray sum is: " << maxSum << endl;
    return 0;
}

// Output
The maximum subarray sum is: 6

Complexity Analysis:

• Time Complexity:O(N^3), where N = size of the array.
  • We are using three nested loops, each running approximately N times.
• Space Complexity:O(1) as we are not using any extra space.

2️⃣ Better Approach (TLE)

Code:

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

int maxSubarraySum(int arr[], int n) {
    int maxi = INT_MIN; // maximum sum

    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            // current subarray = arr[i.....j]

            //add the current element arr[j]
            // to the sum i.e. sum of arr[i...j-1]
            sum += arr[j];

            maxi = max(maxi, sum); // getting the maximum
        }
    }

    return maxi;
}

int main()
{
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxSum = maxSubarraySum(arr, n);
    cout << "The maximum subarray sum is: " << maxSum << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N^2), where N = size of the array.
• Space Complexity:O(1), as we are not using any extra space.

3️⃣ Optimal Approach (Kadane's Algorithm)

A subarray with a sum less than 0 will always reduce our answer and so this type of subarray cannot be a part of the subarray with maximum sum.

Here, we will iterate the given array with a single loop and while iterating we will add the elements in a sum variable. Now, if at any point the sum as 0 we are not going to consider any subarray with negative sum.

Code:

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

long long maxSubarraySum(int arr[], int n) {
    long long maxi = LONG_MIN; // maximum sum
    long long sum = 0;

    for (int i = 0; i < n; i++) {

        sum += arr[i];

        if (sum > maxi) {
            maxi = sum;
        }

        // If sum < 0: discard the sum calculated
        if (sum < 0) {
            sum = 0;
        }
    }

    // To consider the sum of the empty subarray
    // uncomment the following check:

    //if (maxi < 0) maxi = 0;

    return maxi;
}

int main()
{
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    long long maxSum = maxSubarraySum(arr, n);
    cout << "The maximum subarray sum is: " << maxSum << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N), where N = size of the array.
• Space Complexity: O(1), as we are not using any extra space.