Maximum Subarray Sum

Given an array of integers, your task is to compute the maximum sum of a contiguous subarray. This is a classic problem that can be solved efficiently using Kadane's algorithm in \(O(n)\) time. The algorithm works by iterating through the array, at each step updating the maximum subarray sum ending at the current position while keeping track of the overall maximum sum found so far.

The input is provided via standard input (stdin) and the result should be printed to standard output (stdout). The first line of the input 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 empty and the output should be 0.

inputFormat

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

outputFormat

Output a single integer representing the maximum sum of any contiguous subarray. If the array is empty, output 0.

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

6