Tisha Agarwal

Posted on

# Maximum Subarray Sum

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.

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;
}
``````