Maximum Subarray Sum

Given an array of n integers, find the contiguous subarray (containing at least one number) which has the largest sum and output its sum.

This problem can be solved efficiently using Kadane's algorithm. The recurrence relation used is given by:

$$dp_i = \max(a_i, dp_{i-1}+a_i)$$ for \(i \ge 1\) with \(dp_0 = a_0\) and the final answer is \(\max_{0 \le i < n} dp_i\).

inputFormat

The first line contains an integer n, the number of elements in the array. The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer, the maximum contiguous subarray sum.

1
1

1