给定一个序列，要求出一段连续的子序列，是的其和最大或最小。
这是一个很经典的问题，最近做了相关的题目，在这里总结一下。

最直接的一个想法自然是直接暴力枚举每个子段，O(N³)，用前缀和优化一下，这样做的复杂度是O(n²)。在n比较小的时候自然是这种简单易得的方法最好啦。但是人生就是这样子，总不能让你事事如意。然后呢，我们就需要一些更快的方法。

然后我们就发现呢，可以用简单的DP求解，f[i]表示以第i个数为结尾的最大连续子序列和，则可以得到

f[i] = max{f[i-1]+a[i], a[i]}

求最小值自然也可以用同样的方法，这样做的复杂度是O(n)。

看这道题：Sicily p1888:Circular Sequence

题目大意是：给定一个整数的循环序列，求其最大连续子序列和。

对于循环序列，我们一般用的方法是把整个序列复制一遍加到原序列后面，这样这个问题就转化成求得到的新序列的长度不超过原长n的最大连续子序列和(好绕口。。。。)，这个问题我们在后面讨论。这里其实我们可以不利用序列是循环的这个性质，那就只是普通的最大和问题，我们就可以用上面的方法求一遍得到Ans1，然后考虑一下循环的话，那么最大子序列必定是由原序列的一个前缀和一个后缀组成。然后可以发现，剩下的中间那部分其实就是最小连续子序列，所以我们由第二个数到倒数第二个数求一遍最小和(＊)，得到Ans2。最后的答案就是max(Ans1，Sum－ Ans2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <cstdio>
    #include <iostream>
    #include <algorithm>

    using namespace std;

    typedef long long LL;

    const int MN = 100000;

    int a[MN];
    int n = 0, t;

    LL max_sum() {
        LL ret = a[0];
        LL tmp = a[0];
        for (int i = 1; i < n; i++) {
            if (tmp < 0) {
                tmp = a[i];
            } else {
                tmp += a[i];
            }
            ret = max(ret, tmp);
        }
        return ret;
    }

    LL min_sum() {
        if (n <= 2) {
            return 0;
        }
        LL ret = a[1];
        LL tmp = a[1];
        for (int i = 2; i < n-1; i++) {
            if (tmp > 0) {
                tmp = a[i];
            } else {
                tmp += a[i];
            }
            ret = min(ret, tmp);
        }
        return ret;
    }

    int main(){
        cin >> t;
        while (t--) {
            cin >> n;
            LL sum = 0;
            for (int i = 0; i < n; i++){
                scanf("%d", &a[i]);
                sum += a[i];
            }
            LL ans = max(max_sum(), sum - min_sum());
            printf("%lld\n", ans);
        }
        return 0;
    }


在西西里上一开始用I64d输出，一直WA。。。时不时总要被这样的东西坑一下TAT

－－－－－－－－－－－－－－－我是华丽的分割线－－－－－－－－－－－－－－－

接着填一下上面留下的坑。

在求子序列和的时候，如果给定子序列长度的上下界又该怎么做。

同样使用动态规划的解法，我们可以列出方程f[i] = max{sum[i] - min(sum[j - 1])} ，这样做是O(n²),显然不是我们想要的，然后呢我们就可以用单调队列来优化啦～

对于长度的上界MX就是直接的来咯，然后下界MI就利用一个小技巧，从MI开始枚举，然后i-MI入队，这样就保证了序列的长度不小于MI了，每次更新完队首就是符合条件的min(sum[j - 1])了。如果还是不大理解具体可以看代码理解一下。

这里求的是最小连续子序列和：Sicily p1800 [Sequence](http://soj.me/1800)


    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>

    using namespace std;

    const int MN = (1 << 15) + 10;

    int sum[MN] = {0};
    int f[MN] = {0};

    int main() {
        int n, l, r, mi, mx, ans, k;
        cin >> n;
        while (n) {
            scanf("%d%d", &mi, &mx);
            for (int i = 1; i <= n; i++) {
                scanf("%d", &k);
                sum[i] = sum[i-1] + k;
            }
            l = r = 0;
            f[++r] = 0;
            ans = 2147483647;
            for (int i = mi; i <= n; i++) {
                while (l < r && i - f[l+1] > mx) l++;
                while (l < r && sum[f[r]] <= sum[i-mi]) r--;
                f[++r] = i - mi;
                ans = min(ans, sum[i] - sum[f[l+1]]);
            }
            printf("%d\n", ans);
            cin >> n;
        }
        return 0;
    }