Maximum Subarray Sum

You are given an array of integers representing the glowing intensities of pumpkins. Your task is to find the maximum sum of a contiguous subarray using Kadane's Algorithm.

Formally, given an array \(a_1, a_2, \dots, a_n\), you need to compute the value:

\(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k\)

The subarray can consist of a single element if that gives the maximum sum. It is guaranteed that the input contains at least one number.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains an integer \(n\), representing the number of pumpkins.
2. The second line contains \(n\) space-separated integers, each representing the glowing intensity of a pumpkin.

outputFormat

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

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

6