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

Task:
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


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;
}