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)