Maximum Subarray Sum

You are given an array of integers representing sentiment scores. Your task is to compute the maximum sum of a contiguous subarray. This classic problem can be solved with Kadane’s algorithm.

Given an integer array ( A = [a_1, a_2, \dots, a_n] ), find the maximum sum among all contiguous subarrays, i.e.,
( \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k ).

inputFormat

The input begins with a single integer ( n ) ((1 \leq n \leq 10^5)) representing the number of elements in the array. The next line contains ( n ) space-separated integers denoting the array elements.

outputFormat

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

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

6