Maximum Contiguous Subarray Sum

You are given a sequence of integers representing the values on cards. Your task is to find the maximum sum of a contiguous subarray within this sequence. In other words, you need to identify a contiguous segment in the array such that the sum of its elements is maximized.

This problem can be efficiently solved using Kadane's Algorithm. The key recurrence in Kadane's algorithm is given by:

where a_i is the i-th element of the array. The overall answer is the maximum value of maxEndingHere obtained during the iteration.

inputFormat

The first line contains an integer n representing the number of cards. The second line contains n space-separated integers representing the values on the cards.

outputFormat

Output a single integer representing the maximum sum of any contiguous subarray from the given list of card values.

5
-2 1 -3 4 -1

4