Maximum Subarray Sum with Tie-Breaker by Length

Given an array of integers, your task is to compute the maximum sum of any contiguous subarray. In the event that multiple subarrays yield the same maximum sum, you should consider the subarray with the greatest length (this tie‐breaking condition is used internally), though you are only required to output the maximum sum.

This problem can be efficiently solved using a modified version of Kadane's algorithm. As you iterate through the array, if the ongoing sum becomes negative, restart the sum with the current element; otherwise, extend the current subarray. Additionally, if the current subarray sum equals the maximum sum found so far, update the length tracker to record the longest subarray. Finally, output the maximum sum encountered.

inputFormat

The first line contains an integer n indicating 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 sum of any contiguous subarray.

1
1

1