# HackerEarth Mehta And Subarrays problem solution

In this HackerEarth Mehta And Subarrays problem solution This time your task is simple.

Mehta has to find the longest subarray whose sum is greater than equal to zero in a given array of length** N**. After he finds out the length of longest subarray, he has to report how many subarrays of such maximum length exist that satisfy the mentioned property.

Note:
Subarray is defined as an array of contiguous numbers in a particular array. Subarray(A,B) has length (B-A+1) and consists of all numbers from index A to index B.

## HackerEarth Mehta And Subarrays problem solution.

`#include <bits/stdc++.h>using namespace std;vector < pair<long long, int> > v;int n;int main(){    int n,len,cnt,mn;    long long sum,x;    sum = len = cnt = 0;    cin >> n;    v.push_back(make_pair(0,1));    for ( int i = 1; i <= n; i++ ) {        cin >> x;        sum += x;        v.push_back(make_pair(sum,i+1));    }    sort(v.begin(),v.end());    mn = v[0].second;    for ( int i = 1; i <= n; i++ ) {        int val = max(0,v[i].second-mn);        if ( val > len ) {            len = val;            cnt = 1;        }        else if ( val == len ) cnt++;        mn = min(mn,v[i].second);    }    if ( len == 0 ) cout << "-1" << endl;    else cout << len << " " << cnt << endl;    return 0;}`

### Second solution

`#include <cstdio>#include <cmath>#include <iostream>#include <set>#include <algorithm>#include <vector>#include <map>#include <cassert>#include <string>#include <cstring>#include <queue>using namespace std;#define rep(i,a,b) for(int i = a; i < b; i++)#define S(x) scanf("%d",&x)#define P(x) printf("%d\n",x)typedef long long int LL;typedef pair<LL, int > pli;const int N = 100001;LL A[N];int main() {    int n;    S(n);    assert(n > 0 && n < 1000001);    rep(i,1,n+1) {        cin >> A[i];        assert(A[i] >= -1000000000 && A[i] <= 1000000000);        A[i] += A[i-1];    }    vector<pli > st;    int mx,cnt;    mx = cnt = 0;    rep(i,1,n+1) {        if(!st.size() || st.back().first > A[i])            st.push_back(make_pair(A[i], i));        int cur;        if(A[i] >= 0) {            cur = i;        } else {            int lo = 0;            int hi = (int)st.size() - 1;            int idx = -1;            while(lo <= hi) {                int mi = (lo + hi) >> 1;                if(st[mi].first <= A[i]) {                    idx = st[mi].second;                    hi = mi - 1;                } else {                    lo = mi + 1;                }            }            cur = i - idx;        }        if(cur > mx) {            mx = cur;            cnt = 0;        }        if(cur == mx)            cnt++;    }    if(mx == 0) {        P(-1);    } else {        printf("%d %d\n",mx, cnt);    }    return 0;}`