Largest Sum Contiguous Subarray

December 7, 2021

Largest Sum Contiguous Subarray

In the Largest Sum Contiguous Subarray problem we have to find the subarray with maximum sum. It is a very famous problem which is asked in many interviews. In this article, we will provide a C++ solution with an explanation.

Largest Sum Contiguous Subarray Problem Description

We are given an array with n integers. Output the maximum possible subarray sum.

Input

First line contains single integer n the size of subarray.
Second line contains n integers – the elements of subarray.

Output

The required sum.

Largest Sum Contiguous Subarray Solution

Basic Approach –

The basic or naive approach is to use a nested loop and find sum for all sub arrays generated.

Time Complexity – O(n^2)

Space Complexity – O(n)

Optimized Approach

The optimized approach uses Kadane’s Algorithm. The idea of kadane’s algorithm is simple. We maintain two sums –

Current Sum – Csum
Max Sum – MxSum

We iterate over the array adding current element to the current sum. If at any point the current sum becomes negative we set it to zero.

Time Complexity – O(n)

Space Complexity – O(n)

Code

#include <bits/stdc++.h>
using namespace std;
int kadaneAlgo(int arr[], int n)
{
    int cSum = 0, mxSum = INT_MIN;

    // Finding the maximum element
    for (int i = 0; i < n; i++)
        mxSum = max(arr[i], mxSum);
    //Since the maximum element is negative
    if (mxSum <= 0)
        return mxSum;

    // Kadane’s Algorithm
    for (int i = 0; i < n; i++)
    {
        cSum += arr[i];
        if (cSum < 0)
            cSum = 0;
        mxSum = max(mxSum, cSum);
    }
    return mxSum;
}
int main()
{
    int n;
    cin >> n;
    int arr[n];

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << kadaneAlgo(arr, n) << endl;

    return 0;
}

Output

6
1 2 -5 4 -1 100
103