Busca pela soma máxima de submatriz com permutações

C# Medium arrays

Tarefa «Busca pela soma máxima de submatriz com permutações»

Dado um array de inteiros. É permitido realizar no máximo uma operação: escolher dois elementos do array e trocá-los de lugar. Encontre a soma máxima possível de um submatriz contínua (de qualquer comprimento, incluindo 0) após realizar no máximo uma permutação. Se a soma puder ser negativa, imprima 0. O comprimento do array é de 1 a 10^5, os elementos vão de -10^4 a 10^4.

Formato de Entrada

A primeira linha contém um número inteiro N — a quantidade de elementos do array. A segunda linha contém N números inteiros separados por espaços.

Formato de Saída

Um número inteiro — a soma máxima da submatriz.

Exemplos

Exemplo 1

ENTRADA

3
-1 -2 -3

SAÍDA

0

Exemplo 2

ENTRADA

5
1 2 3 4 5

SAÍDA

15

Exemplo 3

ENTRADA

4
-1 2 3 -4

SAÍDA

5

main.cs