Question
Traveler’s Best Energy
A traveler begins a journey along a straight road divided into n checkpoints.
You are given an array a of size n, where a[i] represents the energy gained (if a[i]>0) or lost (if a[i]<0) at the i-th checkpoint.
The traveler always starts from the first checkpoint and may choose to terminate his journey at any checkpoint along the way.
The total energy collected from the start up to the stopping point is called the current energy.
Your task is to determine the maximum energy the traveler can have at any moment during the journey.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the number of checkpoints.
The second line contains KaTeX can only parse string typed expression integers
KaTeX can only parse string typed expression — where each value represents the energy gained (positive) or lost (negative) at a checkpoint.
The second line contains KaTeX can only parse string typed expression integers
KaTeX can only parse string typed expression — where each value represents the energy gained (positive) or lost (negative) at a checkpoint.
Output
Print a single integer: the maximum energy the traveler achieves.
Example
Input
5
2 -1 3 -4 5
Output
5
Explanation:
As the traveler moves forward, the energy levels are:
After checkpoint 1 → 2
After checkpoint 2 → 1
After checkpoint 3 → 4
After checkpoint 4 → 0
After checkpoint 5 → 5
The highest energy reached during the journey is 5.
5
2 -1 3 -4 5
Output
5
Explanation:
As the traveler moves forward, the energy levels are:
After checkpoint 1 → 2
After checkpoint 2 → 1
After checkpoint 3 → 4
After checkpoint 4 → 0
After checkpoint 5 → 5
The highest energy reached during the journey is 5.