Санаа/Hint 1 :

Яг нэг хүүхэд Санта Клаусаар сонгогдохгүй үлдэнэ. Тэр хүүхэд аль нь байхыг тогтоосны дараа үлдсэн хүүхдүүдийн талаар юу хэлж болох вэ?

Шийдэл :

n-1 хүүхэд Санта Клаусаар сонгогдох бөгөөд нэг нь сонгогдохгүй үлдэнэ. Сонгогдохгүй хүүхэд бүрийн хувьд хамгийн оновчтой утгыг тооцоолоод эцэст нь хариуг олж болно.

Эхлээд тэмдэглэх зүйл: дараалалд хамгийн эхэнд зогсох хүүхэд үргэлж +a_i хувь нэмэр оруулна (хэрэв тэр сонгогдохгүй хүүхэд биш бол). Сонгогдохгүй хүүхдийн баруун талд байгаа хүүхэд бүр зөвхөн муу хүүхдийн жагсаалтад орсноор л сонгогдож чадна, учир нь сонгогдохгүй хүүхэд үргэлж тэдний өмнө дараалалд байна. Тиймээс эдгээр хүүхдүүдийн X-д оруулах хувь нэмэр бүгд -a_i байна.

Эхний хүүхэд болон сонгогдохгүй хүүхдийн хооронд байгаа хүүхдүүдийн хувьд, a_i сайхан байдалтай хүүхдийг сайн эсвэл муу жагсаалтад оруулснаар тэдний X-д нэмэх хувь нэмэр +a_i эсвэл -a_i байж болно. Энэ хүрээний хүүхэд бүрийн тэмдгийг бие даан сонгох боломжтой бөгөөд ямар сонголт хийсэн ч хүчинтэй тохиргоо болно. Үүнийг бид барилдлагаар нотолж болно: хүүхэд бүрт хүссэн тэмдгээ тодорхойлсны дараа дараах стратегийг хэрэглэнэ. Хэрэв хоёр дахь хүүхдийг сөрөг байлгахыг хүсвэл 2-р төрлийн үйлдэл хийнэ (хоёр дахь хүүхдийг муу жагсаалтад оруулна). Эс бөгөөс 1-р төрлийн үйлдэл хийж эхний хүүхдийг сайн жагсаалтад оруулна. Хоёр дахь тохиолдолд эхний байрт шилжин орох шинэ хүүхэд нь эерэг хувь нэмэр оруулахыг хүссэн хүүхэд эсвэл тогтоосон сонгогдохгүй хүүхэд байна. Нийт оноог дээд зэргээр нэмэгдүүлэхийн тулд эхний болон сонгогдохгүй хүүхдийн хоорондох хүүхэд бүрийн утгыг max(+a_i,-a_i)=|a_i| болгоно. Хэрэв сонгогдохгүй хүүхдийн сонголт бүрийн хамгийн оновчтой утгыг шууд тооцоолбол O(n^2) цаг шаардагдана. Үүнийг оновчтой болгохын тулд угтвар/дагавар нийлбэрийг ашиглаж болно. |ai|-ийн угтвар нийлбэрийг (a_1 нь үнэмлэхүй/absolute утгагүй тул түүнийг оролцуулахгүйгээр) болон -a_i-ийн дагавар нийлбэрийг урьдчилан тооцоолвол, тогтоосон сонгогдохгүй хүүхэд бүрийн хувьд X-ийн хамгийн их утгыг дараах байдлаар тооцоолж болно: сонгогдохгүй хүүхдийн өмнөх |ai|-ийн угтвар нийлбэр дээр сонгогдохгүй хүүхдийн дараах -a_i-ийн дагавар нийлбэрийг нэмнэ (хэрэв сонгогдохгүй хүүхэд эхнийх нь биш бол a1-ийг нэмнэ).

Код :

#include <bits/stdc++.h>
#define int long long
using namespace std;

void problem () {
    int n; cin >> n;
    int a[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int presum[n + 1];
    presum[0] = 0;
    presum[1] = a[1];
    for (int i = 2; i <= n; i++) {
        presum[i] = presum[i - 1] + abs(a[i]); 
    }
    int sufsum[n + 2];
    sufsum[n + 1] = 0;
    for (int i = n; i >= 1; i--) {
        sufsum[i] = sufsum[i + 1] - a[i];
    }
    int ans = -1E18;
    for (int i = 1; i <= n; i++) {
        ans = max(presum[i - 1] + sufsum[i + 1], ans);
    }
    cout << ans << '\n';
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while(t--) {
        problem();
    }
}