Maximum Subarray Sum

You are given an array of m integers. Your task is to find the maximum sum of any contiguous subarray. Formally, given an array \(b_1, b_2, \dots, b_m\), you need to compute:

\(\max_{1 \leq i \leq j \leq m} \sum_{k=i}^{j} b_k\)

This is a classic problem often solved using Kadane's algorithm. If all numbers are negative, the answer is the maximum element among them.

inputFormat

The first line of the input contains a single integer m representing the number of elements in the array. The second line contains m space-separated integers \(b_1, b_2, \dots, b_m\) representing the array.

outputFormat

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

5
1 -2 3 4 -1

7