Friday, June 18, 2021
Home coding Write a program to find maximum subarray of array.

Write a program to find maximum subarray of array.

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

Please enter your comment!
Please enter your name here

- Advertisment -

Most Popular

Recent Comments