Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

__Example 1:__

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

To solve this question click here:(https://leetcode.com/problems/maximum-subarray/)

Though it is a **EASY LEVEL** question but is really very important.

**Brute force Approach:**

*Time Complexity: O(n^3)*

**C++ CODE:**

```
#include<iostream>
#include<climits>
using namespace std;
int main()
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int maxSum=INT_MIN;
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
int sum=0;
for(int k=i;k<=j;k++)
sum+=arr[k];
maxSum=max(sum,maxSum);
}
}
cout<<maxSum<<endl;
return 0;
}
```

This question can be solved in an optimized way by using **Kadane Algorithm.**

*The simple idea of Kadaneβs algorithm is to look for all positive contiguous segments of the array. And keep track of maximum sum contiguous segment among all positive segments*

**C++ CODE:**

```
#include<iostream>
#include <climits>
using namespace std;
int main()
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int currSum=0;
int maxSum=INT_MIN;
for(int i=0;i<n;i++)
{
currSum+=arr[i];
if(currSum<0)
currSum=0;
maxSum=max(maxSum,currSum);
}
cout<<maxSum<<endl;
return 0;
}
```

## Top comments (0)