Taco's Maximum Subarray Problem

In this problem, you are given an array of integers. Your task is to find the contiguous subarray (containing at least one number) which has the largest sum and output that sum.

The well-known Kadane's algorithm can solve this in O(n) time. Mathematically, the maximum subarray sum is defined as:

$$\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k$$

where \(a_k\) represents each element of the array.

Your program will read an integer n representing the number of elements, followed by n space-separated integers, and then print the maximum subarray sum.

inputFormat

The input consists of two lines:

• The first line contains a single integer n (the number of elements in the array).
• The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer, which is the maximum subarray sum.

1
1

1