##### Cricket Rating

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.

India is a cricket crazy nation. Chang also loves cricket and computations related to cricket. Chang has created a Cricket app.This app analyses the performance of a cricketer. If a cricketer under-performs, then a negative rating is awarded. If performance is good, then positive rating is awarded to the cricketer.Chang wants to analyse the performance of a cricketer over a period of

N

N matches. Chang wants to find consistency of a cricketer. So he wants to find out the maximum consistent sum of cricket rating of a batsman or a bowler only if his overall rating is positive over that period. Help chang in doing so.

Input

The first line contain number of matches “N” over which the analysis is to be done. The second line contains those ratings of a batsman/bowler in those N matches.

Output

Print a single integer ie. the maximum consistent sum of rating of the cricketer if it is positive otherwise output 0 (zero).

Constraint

0≤N(matches)≤10^5

-100≤rating≤+100

#include <iostream> using namespace std; int maxSubArraySum(int a[], int size) { int max_so_far = 0, max_ending_here = 0; for (int i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; if (max_ending_here < 0) max_ending_here = 0; if (max_so_far < max_ending_here) max_so_far = max_ending_here; } return max_so_far; } int main() { int n; cin>>n; int *a = new int[n]; for(int i=0;i<n; i++) cin>>a[i]; int max_sum = maxSubArraySum(a, n); if (max_sum>0) cout<<max_sum; else cout<<0; return 0; }