Maximum Magic Power

You are given an integer n representing the number of houses and an array of n integers. Each integer represents the magic power of a house. Your task is to determine the maximum sum of a contiguous subarray. In other words, find the maximum attainable magic power by summing a consecutive segment of houses.

This problem is a classic application of Kadane's algorithm. The problem can be mathematically expressed as follows:

$$ \text{max\_sum} = \max_{1 \leq i \leq j \leq n} \left( \sum_{k=i}^{j} a[k] \right) $$

Use efficient algorithms to ensure your solution performs well even for large inputs.

inputFormat

The input is provided via standard input (stdin) in the following format:

• The first line contains a single integer n indicating the number of houses.
• The second line contains n integers separated by spaces, representing the magic power of each house.

outputFormat

Output a single integer to standard output (stdout), which is the maximum sum of any contiguous subarray of the given array.

5
-3 2 -1 4 -5

5