Largest Sum Subarray

Given an array of integers, your task is to find the sum of the contiguous subarray which has the largest sum. This is a classic problem that can be solved efficiently using Kadane's algorithm. The core idea of Kadane's algorithm is to iterate through the array and, at each step, determine whether it is more beneficial to add the current element to the existing subarray or start a new subarray with the current element. Mathematically, for each index \(i\), the recurrence is given by:

\[ max\_current = \max(a_i, max\_current + a_i)\]

If the array is empty, the output should be 0.

inputFormat

The input is read from standard input and has the following format:

• The first line contains a single integer \(N\), denoting the number of elements in the array.
• If \(N > 0\), the second line contains \(N\) space-separated integers representing the elements of the array. If \(N = 0\), there is no second line.

outputFormat

Output to standard output a single integer that represents the sum of the contiguous subarray with the largest sum.

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

7