【POJ1050+POJ2018+HDOJ6638+牛客1006D】最大子段和问题

（1）POJ1050-经典最大子段和问题

POJ1050
题目： 求给定矩阵的最大子矩阵和， $n \leq 100$
解题思路： 由于n非常小，完全可以 $O (n^{3})$ 来做。枚举矩阵的上下界，处理出当前上下界下，每一列的和，按照经典思路：扫描每一列的和，不断加入子段，当子段和变为负数时，将当前的整个子段清空，再重新加入，不断更新答案。
ac代码：

#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <climits>
using namespace std;
typedef long long ll;
const int maxn = 110;
int a[maxn][maxn], c[maxn], s[maxn];
int n, ans = INT_MIN;
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)//枚举子矩阵的起末行号，并求出当前i~j行内的列值
        {
            memset(c, 0, sizeof(c));
            memset(s, 0, sizeof(s));
            for(int k = 1; k <= n; k++)
                for(int p = i; p <= j; p++)
                    c[k]+=a[p][k];
            //当子段和变为负数时清空,否则继续加入
            for(int k = 1; k <= n; k++)
            {
                s[k] = s[k-1]>0 ? s[k-1]+c[k] : c[k];
                ans = max(ans, s[k]);
            }

        }
    }
    printf("%d\n", ans);
    return 0;
}

(2)POJ2018-长度不小于F的最大子段和

POJ2018
题目： $N (1 \leq N \leq 1 e 5)$ 个农场，每个农场有 $c o w s$ 头牛，选择几个连续的一些农场，满足农场数 $\geq F$ ，且这些农场的牛的平均值最大，求最大值。
解题思路： 二分答案。子段和可以利用前缀和转化为：
$<munder> \max i - j \geq F </munder> {A_{j + 1} + A_{j + 2} + . . . + A_{i}} = <munder> \max F \leq i \leq n </munder> {s u m_{i} - <munder> \min 0 \leq j \leq i - F </munder> {s u m_{j}}}$
随着i的增加，j的取值范围每次只增加1，相当于 $\min {s u m_{j}}$ 每次只会加入一个新的值，所以可以在 $O (n)$ 内处理出子段长度不小于F的最大子段和。
若当前二分答案为 $x$ ，由 $\frac{\sum 子段和}{长度 L} = x$ 得 $\sum 子段和 - 长度 L * x = p = 0$ ，（相当于把每个 $c o w s - x$ 再求最大子段和）。若 $p > = 0$ 则可继续扩大答案，否则缩小答案。
ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
const double eps = 1e-5;
int n, f;//至少包含f个fields
double a[maxn], sum[maxn], b[maxn];
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d %d", &n, &f);
    for(int i = 1; i <= n; i++)
        scanf("%lf", &a[i]);
    double l = 0, r = 1e6;
    while(r-l>eps)
    {
        double mid = (l+r)/2;
        for(int i = 1; i <= n; i++)
        {
            b[i] = a[i]-mid;
            sum[i] = sum[i-1]+b[i];
        }
        double MAX = -1e10;//长度>=f的最大连续子段和
        double MIN = 1e10;
        for(int i = f; i <= n; i++)
        {
            MIN = min(MIN, sum[i-f]);
            MAX = max(MAX, sum[i]-MIN);
        }
        if(MAX>=0) l = mid;
        else r = mid;
    }
    printf("%d\n", (int)(r*1000));
    return 0;
}

(3)HDOJ6638-线段树维护最大子段和

HDOJ6638
题目： 给定 $n$ 个点的坐标 $(x, y)$ 和权值 $w$ ，求最大子矩阵权值和。 $- 1 e 9 \leq x, y, w \leq 1 e 9, \sum n \leq 10000$ 。
解题思路： $n$ 比较大，不能 $O (n^{3})$ 暴力枚举了，需要将二维转为一维， $O (n^{2} l o g n) 来解决。$ 将所有 $y$ 离散化，点的 $y$ 值修改为 $r a n k y$ ，再将所有点按照 $x$ 从小到大排序，这样处理出来的点的顺序如下：

先枚举起点，以A为起点建线段树，当在线段树上插入完{A,B,C}后查询线段树上当前区间的最大子段和，当插入完{A,B,C,D,E,F}和{A,B,C,D,E,F.G,H,I}时分别查询答案；同理以D为起点建立线段树，当插入完{D,E,F}和{D,E,F,G,H,I}时分别查询查询答案；以G为起点建立线段树，插入完{G,H,I}时查询答案。
ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e3+10;
struct point{
    int x, y, w;
    point(){};
    friend bool operator < (point a, point b)
    {
        return a.x==b.x ? a.y<b.y : a.x<b.x;
    }
}p[maxn];
struct node{
    int l, r;
    ll mx, max_pre, max_suf, sum;//区间最大子段和，最大前缀和，最大后缀和，总和
}tree[maxn<<2];
int y[maxn];
int t, n;
void build(int id, int l, int r)
{
    tree[id].l = l; tree[id].r = r;
    tree[id].sum=tree[id].max_pre=tree[id].max_suf=tree[id].mx=0;
    if(l==r) return ;
    int mid = (l+r)>>1;
    build(id<<1, l, mid);
    build(id<<1|1, mid+1, r);
}
void push_up(int id)
{
    tree[id].sum = tree[id<<1].sum+tree[id<<1|1].sum;
    tree[id].max_pre = max(tree[id<<1].max_pre, tree[id<<1].sum+tree[id<<1|1].max_pre);
    tree[id].max_suf = max(tree[id<<1|1].max_suf, tree[id<<1|1].sum+tree[id<<1].max_suf);
    //最大子段和mx=max(左区间mx, 右区间mx, 左区间最大后缀和+右区间最大前缀和)
    tree[id].mx = max(max(tree[id<<1].mx, tree[id<<1|1].mx), tree[id<<1].max_suf+tree[id<<1|1].max_pre);
}
void insert(int id, int k, int w)//从id=1开始给y排名为k的叶子节点+w
{
    if(tree[id].l==tree[id].r)
    {
        tree[id].sum=tree[id].max_pre=tree[id].max_suf=tree[id].mx=tree[id].mx+w;
        return ;
    }
    int mid = (tree[id].l+tree[id].r)>>1;
    if(k<=mid) insert(id<<1, k, w);
    else insert(id<<1|1, k, w);
    push_up(id);
}

int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &t);
    while(t--)
    {
        ll ans = LONG_LONG_MIN;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].w);
            y[i] = p[i].y;
        }
        sort(y+1, y+1+n);
        int num = unique(y+1, y+1+n)-(y+1);
        for(int i = 1; i <= n; i++)
            p[i].y=lower_bound(y+1, y+1+num, p[i].y)-y;
        sort(p+1, p+1+n);//y离散化后，按x从小到大排序
        for(int i = 1; i <= n; i++)
        {
            if(i!=1 && p[i].x==p[i-1].x) continue;//不建重复的树
            build(1, 1, num);
            for(int j = i; j <= n; j++)
            {
                if(j!=i && p[j].x!=p[j-1].x) ans = max(ans, tree[1].mx);
                insert(1, p[j].y, p[j].w);
            }
            ans = max(ans, tree[1].mx);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

（4）长度不小于m的最大连续子序列和

传送门
题目： 给定长度为n的整数序列，找到最大的长度不超过m的连续子序列和，n,m≤3e5
解题思路： 固定子序列[j, i]的右端点i，那么 $j \in [i - m + 1, i]$ 且子序列[j,i]内的和利用前缀和可以转化为 $s u m [i] - s u m [j - 1]$ 。i一定，sum[j-1]最小，连续子序列和最大。令J=j-1， $J \in [i - m, i - 1]$ 。在枚举i的过程中，J的区间每次右移一位，每次都在相应的区d间内找最小值，这样这道题就转化成了洛谷P1886滑动窗口那道题，用单调队列来做，队头存最小值。
注意队列里要先放一个0，因为i是先取到最小值（最小值是在队列非空的时候才取得到）后再存入。
ac代码：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 3e5+10;
deque<int> q;//队头最大/小值
int n, m;
ll sum[maxn];
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lld", &sum[i]), sum[i]+=sum[i-1];
    ll ans = LLONG_MIN;
    //在[i-m, i-1]中找最小的sum[J]
    q.push_back(0);
    for(int i = 1; i <= n; i++)
    {
        while(!q.empty() && sum[q.back()]>sum[i]) q.pop_back();
        while(!q.empty() && q.front()<i-m) q.pop_front();
        if(!q.empty()) ans = max(ans, sum[i]-sum[q.front()]);
        q.push_back(i);
    }
    printf("%lld\n", ans);
    return 0;
}