Maximum Subarray Sum

Given an array of integers, find the contiguous subarray that has the largest sum. This is a classic problem often solved using Kadane's Algorithm.

The problem can be expressed mathematically as:

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

Your task is to implement an efficient algorithm that computes this maximum sum in O(n) time.

inputFormat

The first line contains a single integer n representing the number of elements in the array.

The second line contains n space-separated integers, which are the elements of the array.

outputFormat

Output a single integer, which is the sum of the maximum subarray.

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

6