```html <pre><code>أقصى مجموع لصفيف فرعي مع حذف عنصر واحد</code></pre> ```

Java Hard arrays

مهمة «```html <pre><code>أقصى مجموع لصفيف فرعي مع حذف عنصر واحد</code></pre> ```»

بالنظر إلى مصفوفة أعداد صحيحة. يجب إيجاد أقصى مجموع لمصفوفة فرعية (تسلسل متواصل من العناصر) بشرط أنه يمكن حذف عنصر واحد على الأكثر (أو عدم حذف أي عنصر). يجب أن تحتوي المصفوفة الفرعية على عنصر واحد على الأقل. المطلوب تنفيذ خوارزمية بتعقيد زمني O(n) وذاكرة إضافية ثابتة.

تنسيق الإدخال

السطر الأول يحتوي على عدد صحيح n (1 ≤ n ≤ 10^5) — عدد عناصر المصفوفة. السطر الثاني يحتوي على n من الأعداد الصحيحة، مفصولة بمسافات — عناصر المصفوفة (قيمتها المطلقة لا تتجاوز 10^4).

تنسيق الإخراج

عدد صحيح واحد — أقصى مجموع ممكن للمصفوفة الفرعية بعد حذف عنصر واحد على الأكثر.

أمثلة

مثال 1

الإدخال

5 1
1 2 3 2 4

الإخراج

9

مثال 2

الإدخال

2
7 1
-4 3

الإخراج

8

مثال 3

الإدخال

6
2 -1 2 3 4 -5

الإخراج

11

main.java