Maximum Subarray Sum

Given an array of integers, your task is to compute the maximum sum of any contiguous subarray. A contiguous subarray is defined as a sequence of consecutive elements from the array, and it should contain at least one number. If the array is empty, output None.

This problem is classically solved by Kadane's algorithm. Mathematically, the maximum subarray sum can be expressed as: $$\max_{1 \le i \le j \le n} \sum_{k=i}^{j} a_k$$

inputFormat

The input is read from standard input (stdin) as follows:

1. The first line contains an integer n, the number of elements in the array.
2. If n > 0, the second line contains n space-separated integers representing the array elements.

outputFormat

Output a single line to standard output (stdout) containing the maximum sum of a contiguous subarray. If the array is empty (n = 0), output None.

4
1 2 3 4

10