51Nod1050 循环数组最大子段和/Problem a

51Nod1050

20181105A problem.pdf

如果最大子段和跨过了$n$，必然是中部有一段小于$0$的区间造成无法扩展，全部取反求出这一段区间，与原数列总和相加即可得到，最后与非循环的最大子段和取$\max$。

#include<cstdio>
#if _WIN32||__WIN32__||_WIN64||__WIN64__||__CYGWIN__
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#if __unix__
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#if __GNUC__
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#define inline __attribute__((always_inline))
#endif
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void putc(char x) { *oS++ = x; }
    char gc() {
        if (iS == iT)iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
        return *iS++;
    }
    template<class T>T rd() {
        int c = gc(), f = 1;
        T x = 0;
        for (; c < 48; c = gc())if (c == '-')f = -1;
        for (; c > 32; c = gc())x = x * 10 + (c & 15);
        return x * f;
    }
    template<class T>void print(T x) {
        if (!x) { *oS++ = '0'; return; }
        int tp = 0;
        for (; x; st[++tp] = x % 10 + 48, x /= 10);
        for (; tp; *oS++ = st[tp--]);
    }
    io() :oS(obuf), oT(obuf + L - 1) {
#ifndef ONLINE_JUDGE
        freopen("a.in", "r", stdin), freopen("a.out", "w", stdout);
#endif
    }
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int n = ip.rd<int>(), a[1000001], b[1000001];
long long sum;
inline long long gao(int*x) {
    long long cur = 0, ret = 0;
    for (int i = 1; i <= n; ++i) {
        cur += x[i];
        if (cur < 0)cur = 0;
        if (ret < cur)ret = cur;
    }
    return ret;
}
template<class T>inline T max(T a, T b) { return a > b ? a : b; }
int main() {
    for (int i = 1; i <= n; ++i)sum += (a[i] = ip.rd<int>()), b[i] = -a[i];
    ip.print(max(gao(a), sum + gao(b)));
}