Maximum Contiguous Subarray Sum

You are given an array of integers. Your task is to compute the maximum sum of any contiguous subarray. This is a classic problem that can be solved efficiently using Kadane's algorithm.

The recurrence relation for Kadane's algorithm is given by:

where dp[i] represents the maximum sum of any contiguous subarray ending at index i, and a[i] is the i-th element of the array.

If the input array is empty then the maximum contiguous sum is defined as 0.

inputFormat

The first line of input contains an integer n denoting the number of elements in the array.

The second line contains n space-separated integers representing the array elements. If n is 0, the second line may be empty.

outputFormat

Output a single integer representing the maximum contiguous subarray sum.

5
1 2 3 4 5

15