Maximum Subarray Sum (Kadane's Algorithm)

Given an array of integers, your task is to determine the maximum sum of any contiguous subarray using Kadane's Algorithm.

Kadane's Algorithm works by iterating through the array and at each position, determining the maximum sum ending at that index by applying the recurrence:
(max_current = \max(\text{num},; max_current + \text{num})).

If the array is empty, consider the maximum sum to be 0. This problem tests your ability to implement dynamic programming concepts and handle edge cases.

inputFormat

The first line of input contains a single integer (n) representing the number of elements in the array. If (n = 0), there is no further input. Otherwise, the second line contains (n) space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the maximum sum of a contiguous subarray. The result should be printed to the standard output.## sample

8
-2 -3 4 -1 -2 1 5 -3

7