# Largest Sum Contiguous Subarray

## 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 cSum = 0mxSum = INT_MIN;

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

for (int i = 0i < ni++)
{
cSum += arr[i];
if (cSum < 0)
cSum = 0;
mxSum = max(mxSumcSum);
}
return mxSum;
}
int main()
{
int n;
cin >> n;
int arr[n];

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

`61 2 -5 4 -1 100103`