Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of any contiguous subarray. This is a classic problem that can be solved using Kadane's Algorithm. Formally, given an array \(A = [a_1, a_2, \dots, a_n]\), you need to compute \(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k\).

The input is provided via standard input (stdin) and the output should be written to standard output (stdout).

inputFormat

The first line of input contains a single integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the elements of the array.

outputFormat

Output a single integer which is the maximum sum of any contiguous subarray of the given array.

10
1 2 3 4 5 6 7 8 9 10

55