Maximum Contiguous Subarray Sum After One Modification

Given an array of integers, you are allowed to perform at most one modification on the array. In this problem, the modification allows you to change one element's value to zero. Your task is to compute the maximum sum of any contiguous subarray after performing this modification.

More formally, let (A = [a_1, a_2, \ldots, a_n]) be the input array. You may choose at most one index (i) ((1 \le i \le n)) and change (a_i) to 0. An empty subarray is considered to have a sum of 0.

This problem can be solved by modifying Kadane's algorithm using dynamic programming. The goal is to determine the maximum contiguous subarray sum achievable after applying the modification at most once.

inputFormat

Input is given in two lines. The first line contains a single integer (n) denoting 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 — the maximum sum of any contiguous subarray after performing at most one modification.## sample

5
1 2 -3 4 5

12