Given an array with negative and positive n element of integers types.
Your task to find the contiguous sub-array with maximum sum.
Example:-
n=4
arr=[4,2,-3,5]
ans=8
now,Out of all ((4),(2),(-3),(5),(4+2),(2+(-3)),((-3)+5),(4+2+(-3)),(2+(-3)+5),(4+2+(-3)+5)) contiguous subarray,The maximum sum of contiguous array is(4+2+-3+5)=8
Approach I(Brute-Force)
The basic approach is to find all the Contigous subarray and then calculate Maximum Sum.
Let us consider a array arr[] of length n and max_ans,temp_sum are the variable for storing answer and temporary answer.
#include<bits/stdc++.h>
using namespace std;
int Max_Subarray(vector<int> &arr)
{
int n=arr.size();
int ans_max=0;
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
int temp_sum=0;
for(int k=i;k<=j;k++)
{
temp_sum+=arr[k];
}
ans_max=max(ans_max,temp_sum);
}
}
return ans_max;
}
int main()
{
int n;
cout<<"Enter the number of element in array:";
cin>>n;
vector<int> arr;
for(int i=0;i<n;i++)
{
int num;
cin>>num;
arr.push_back(num);
}
cout<<"Maximum Subarray:"<<Max_Subarray(arr);
return 0;
}
Approach II(Kadane's Algorithm)
This is optimal solution the idea behind the algorithm is initialize two variable max_sum_before=INT_MIN and max_sum_current=0 and start traversing the array and add the element of array in max_sum_current and
if the max_sum_current is grater then max_sum_before then update max_sum_before and if max_sum_current is less then 0 then update max_sum_current with 0.
Algorithm: Max_Subarray(arr,n)
Step 1:- Initialize max_sum_current=0 and max_sum_before=INT_MIN
Step 2:- Repeat step 3,4,5 from(i=0 to n-1)
Step 3:- max_sum_current+=arr[i]
Step 4:- if max_sum_current>max_sum_before then max_sum_before=max_sum_current
Step 5:- if max_sum_current==0 then max_sum_current=0
max_sum_before is answer.
#include<bits/stdc++.h>
using namespace std;
int Max_Subarray(int arr[],int n)
{
int max_sum_before=INT_MIN,max_sum_current=arr[0];
for(int i=1;i<n;i++)
{
max_sum_current+=arr[i];
if(max_sum_current<max_sum_before)
max_sum_before=max_sum_current;
if(max_sum_current>0)
max_sum_before=0;
}
return max_sum_before;
}
int main()
{
int n;
cout<<"Enter the Number of element in Array:";
cin>>n;
int arr[n];
cout<<"Enter Array Element:";
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<"Sum of Maximum Contigous Subarray:"<<Max_Subarray(arr,n);
}