牛客NOIP暑期七天营-普及组1-D矩阵

题目大意：给定一个n*m的矩阵，输出最大子矩阵（元素之和最大值）。

对于每一个子矩阵，如果左上角是(x, y)，右下角是(p, q)，那么他每一行的元素之和是：

用乘法分配率合并后即：

这样，问题就转化为求数组a中的最大子段和以及数组b中的最大子段和问题了。

当然，还需要注意细节：

1、对于正数：两边都取最大子段和

2、对于负数：两边都取最小子段和

3、一个全正，一个全负：正数取最小值、负数取最大值（绝对值尽量小、乘积绝对值尽量小）

当然，只要某个数列既有正值又有负值，就不会出现第三种情况。

不管怎样，全部求一遍答案就出来了。

最后，关于赋初值：前缀和初值可以是0，因为前0个是可以用的；最大区间和、最小区间和就不能为0，取第一个数做初值比较保险。

#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n, m, i, j, k, l, a[N];
long long x, y, ax, ay, bx, by, s[N];
int main(){
    scanf("%d%d", &n, &m);
    ax = bx = -101, ay = by = 101;
    for(x=y=0, i=1; i<=n; i++){
        scanf("%d", &a[i]);
        s[i] = s[i-1] + a[i];
        ax = max(ax, s[i]-y);//最大区间和 
        ay = min(ay, s[i]-x);//最小区间和 
        x = max(x, s[i]);//前面最大前缀和 
        y = min(y, s[i]);//前面最小前缀和 
    }
    for(x=y=0, i=1; i<=m; i++){
        scanf("%d", &a[i]);
        s[i] = s[i-1] + a[i];
        bx = max(bx, s[i]-y);//最大区间和 
        by = min(by, s[i]-x);//最小区间和 
        x = max(x, s[i]);//前面最大前缀和 
        y = min(y, s[i]);//前面最小前缀和 
    }
    x = max(ax*bx, ay*by);
    y = max(ax*by, ay*bx);
    printf("%lld\n", max(x, y));
    return 0;
}