Maximum Subarray Sum

You are given an array of n integers. Your task is to compute the maximum sum of any contiguous subarray. The answer is defined as:

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

where \(a_1, a_2, \dots, a_n\) are the integers in the array. Note that the subarray must contain at least one element.

An efficient solution to this problem can be obtained using Kadane's algorithm, which runs in \(O(n)\) time.

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\), which represent the elements of the array.

outputFormat

Output a single integer, the maximum sum of any contiguous subarray.

1
1

1