June 26, 2022

Given an integer array we have to find the maximum subarray of array and print the result on screen.

so what is subarray of array?

subarray is a part of array which is contiguous.

Example:

Input:7 6 4 5 0 1
output:23

Logic:

step 1-initalise the maxx element and current maxx element.
step 2-iterate whole array and start adding element to current maxx.
step 3-compare maxx with current maxx and update it.

code:

#include<bits/stdc++.h> 
using namespace std; 
int main() 
{ 
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
    cin>>a[i];
}
int maxx=a[0]; 
int currmax=a[0]; 
for (int i = 1; i < n; i++) 
{
currmax = max(a[i], currmax+a[i]); 
maxx = max(maxx, currmax); 
}
cout<<maxx<<endl;
} 

Output:

6
 7 6 4 5 0 1

output:
23

Time Complexity:O(N)

Space Complexity:O(1)

Leave a Reply

Your email address will not be published.