Maximum Subarray Sum

Given an array of integers, your task is to compute the maximum sum of any contiguous subarray. This problem is a classic example of using Kadane's Algorithm, which efficiently finds the optimal subarray in O(n) time. If the array is empty, the maximum sum is defined to be 0.

Mathematical formulation: Let \( A = [a_1, a_2, \dots, a_n] \) be the given array. Find \( \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \). For an empty array, return 0.

inputFormat

The input is given via standard input (stdin). The first line contains an integer n, representing the number of elements in the array. The second line contains n space-separated integers. If n is 0, the array is considered empty.

outputFormat

Output a single integer to standard output (stdout) representing the maximum sum of any contiguous subarray.## sample

9
-2 1 -3 4 -1 2 1 -5 4

6