Maximum subarray sum of a given array using c++
By Rohit Nandan DubeyIn this C++ tutorial, we are going to discuss the maximum subarray sum of a given array. Firstly we will learn what is subarray?
What is Subarray in C++
A subarray is a contiguous part of an array. It is an array inside another array. For example, consider the array [1, 2, 3], There are 6 non-empty sub-arrays. The subarrays are (1), (2), (3), (1,2), (2,3) and (1,2,3) but (1,3) is not subarray.
Problem Description:
Given an array of n integers a1,a2,…,an, our task is to find the maximum subarray sum of numbers in a contiguous region in the array. The problem is interesting when there may be negative numbers in the array. For example, for the array of values [1, 1, −3, 4, −1, 3, 1, −5, 4], the contiguous subarray with the largest sum is [4, −1, 3, 1], with sum 7.
Solutions of maximum subarray sum of a given array using c++
There are several possible methods for solving this problem with different time complexities. Here we are going to learn three methods.
Method 1 to solve Maximum subarray sum of a given array in C++
This is a direct method to solve the problem is to go through all possible subarray, calculate the sum of the numbers in each subarray and maintain the maximum sum. Implementation of this method :
Time Complexity: O(n^3)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,i,j,k;
//n: size of input array
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
int sum,msum=0;
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
sum=0;
for(k=i;k<=j;k++)
{
sum+=a[k];
}
msum=max(msum,sum);
}
}
cout<<msum<<endl;
return 0;
}Input:
9 -2 1 -3 4 -1 2 1 -5 4
Output:
6
Method:-2
This method is similar to the first method but more efficient. We can make the first method more efficient by removing one loop which is done by calculating the sum at the same time when the right end of the subarray moves. Implementation of this method :
Time Complexity: O(n^2)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,i,j,k;
//n: size of input array
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
int sum,msum=0;
for(i=0;i<n;i++)
{
sum=0;
for(j=i;j<n;j++)
{
sum+=a[j];
msum=max(msum,sum);
}
}
cout<<msum<<endl;
return 0;
}Input:
9 -2 1 -3 4 -1 2 1 -5 4
Output:
6
Method:-3
We can also find the required result in O(n) time, this method is known as Kadane algorithm. Algorithm for this method-
- Initialize : sum=0 and smax=0
Loop for each element of the array
- sum=max(sum+a[i],a[i]);
- smax=max(smax,sum)
Time Compexity: O(n)
Implementation of this method :
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,i,j,k;
//n: size of input array
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
int sum,msum;
for(i=0;i<n;i++)
{
if(i==0)
{
sum=a[i];
msum=sum;
}
else
{
sum=max(sum+a[i],a[i]);
msum=max(sum,msum);
}
}
cout<<msum<<endl;
return 0;
}Input:
9 -2 1 -3 4 -1 2 1 -5 4
Output:
6
Also, learn:
Leave a Reply