Maximum Segment Sum

You are given an array of integers representing book identifiers. Your task is to compute the maximum segment sum, where a segment is defined as a contiguous subarray of the given array. In other words, find the contiguous subarray that has the largest possible sum.

Formally, for an array \(a[0], a[1], \dots, a[n-1]\), you need to find a pair of indices \(i, j\) with \(0 \le i \le j < n\) such that the sum \(a[i] + a[i+1] + \dots + a[j]\) is maximized. In the special case when the array is empty (i.e. \(n = 0\)), output -inf (which represents negative infinity).

This is a classic problem that can be efficiently solved using Kadane's Algorithm.

inputFormat

The first line of input contains a single integer \(n\) representing the number of elements in the array. The second line contains \(n\) integers separated by spaces, representing the elements of the array. If \(n = 0\), the second line may be omitted.

outputFormat

Output a single line containing the maximum segment sum. If the array is empty, output -inf (without quotes).

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

6