Question
The Merchant's Profit Scroll
In the kingdom of Eldoria, a merchant keeps track of his daily profits and losses in a magical scroll.
Each number in the scroll represents the profit or loss made on a particular day.
Your task is to find the maximum total profit the merchant can earn from a contiguous sequence of days.
Input
The first line contains a single integer n — the number of days.
The second line contains n integers — a1, a2, ..., an representing profit or loss for each day.
Output
Print a single integer — the maximum subarray sum.
Example
Example 1:
Input:
The best segment is [2, 3, -2, 4] with total sum 7.
Input:
5
-1 2 3 -2 47The best segment is [2, 3, -2, 4] with total sum 7.