Maximum Subarray Sum

Given a one-dimensional array of integers, the task is to find the maximum sum of a contiguous subarray. This is a classic problem that can be efficiently solved using Kadane's algorithm.

The problem can be mathematically stated as follows:

Given an array \(A = [a_1, a_2, \dots, a_n]\), find the maximum sum over all contiguous subarrays \(A[i \dots j]\), i.e., compute \[ \max_{1 \le i \le j \le n} \left\{ \sum_{k=i}^{j}a_k \right\}. \]

Note that the array may contain both positive and negative integers.

inputFormat

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

outputFormat

Output a single integer representing the maximum sum of a contiguous subarray.

1
1

1