Largest Sum Subarray

Given an integer array \( A \) of length \( n \), your task is to find the sum of the contiguous subarray with the largest sum. An efficient approach to solve this problem is by using Kadane's Algorithm.

The recurrence relation of Kadane's Algorithm is given by:

\( max\_current = \max( a[i],\; max\_current + a[i] ) \)

If the array is empty (i.e. \( n = 0 \)), the output should be \( 0 \).

inputFormat

The first line of input contains an integer \( n \) which represents the number of elements in the array. If \( n > 0 \), the second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

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

6
1 -2 3 5 -3 2

8