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)