Maximum Contiguous Subarray Sum

Given an array of integers, your task is to find the maximum sum of any contiguous subarray within the given array. In other words, if the array is \( a_1, a_2, \ldots, a_n \), you are required to compute

\( \max_{1 \le i \le j \le n} \sum_{k=i}^{j} a_k \)

This problem is a classic example of dynamic programming and can be efficiently solved using Kadane's Algorithm.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer \( n \) (\( 1 \le n \le 10^5 \)) which represents the number of elements in the array.
• The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output a single integer to standard output (stdout): the maximum sum of any contiguous subarray of the input array.

5
1 -3 2 1 -1

3