Maximum Subarray Sum

You are given an array of integers. Your task is to find the contiguous subarray (containing at least one number) which has the largest sum and output its sum.

More formally, if the array is denoted by \(a_1, a_2, \dots, a_n\), find the maximum value of \[ \sum_{i=l}^{r} a_i \] for any \(1 \le l \le r \le n\). This is a classic problem that can be solved efficiently using Kadane's algorithm.

Example:

• Input: [1, -2, 3, 4, -1, 2, 1, -5, 4]
• Output: 9 (which corresponds to the subarray [3, 4, -1, 2, 1])

inputFormat

The first line of input contains an integer \(n\) which is 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 which is the sum of the contiguous subarray with the largest sum.

1
1

1