【练习-9】最大子序列和==＞最大子矩阵和（#若是）

2024-01-19 20:38:16

慢慢来，要讲最大子矩阵和，首先我们要会求最大子序列和，那么问题来了：

什么是最大子序列和？

给定一串数字，任意选择连续的子序列，将子序列各个元素相加求和，能得到的最大值，就是最大子序列和。

举个例子：1 2 3 -2 3 -9 5
在上面这一段数列中最大子序列和是7，最大子序列和对应的子序列是1 2 3 -2 3.

那我们就来说一下如何去操作：
其实很简单，我们只需要把每次的值加起来，如果是大于0的那么就继续保留，小于0的话就清空 在这种情况下每次比较记录和和当前最大值的大小。

为什么要这样操作？

当记录和是大于零的时候，他就会对接下来的数做出贡献。（请记住这句话）
看上面的例子，1 2 3 -2 3 -9 5
到第三个数的时候cnt = 6，接下来我们会碰到一个负数，cnt = 4仍然是大于0的，那么他就会对后面的数做出贡献 （cnt + 3 很明显是比单独一个3大）。
到第六个数的时候cnt = -2, cnt < 0 ，他就不会对后面的数做出贡献 （cnt + 5 < 5）

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
int mx= -1e9;//记录最大和
int x;
int cnt;//记录当前值
int n;//数字个数
int main() 
{
	cin>>n;
	while(n--)
	{
		cin>>x;
		cnt += x;
		if(cnt > mx)	mx = cnt;
		if(cnt < 0)		cnt = 0;
	}
	cout<<mx;
	return 0; 
}

解释：

①记录最大和的变量初始值要定义为足够小的负数（因为可以是负数）
②每次先比较cnt 和 mx 的值再去判断cnt是否小于零（可能全部都是负数）

知道了这个，我们就可以来学习最大子矩阵和了！

最大子矩阵和

这里给出一个题目：

若是

Description

“一生至少该有一次,为了某个人而忘了自己,
不求有结果 ,不求同行,不求曾经拥有,甚至不求你爱我，只求在我最美的年华里,遇到你。” ——徐志摩

原来小 W 和小 K 要到到 Q 镇去游玩。
Q 镇是一个非常浪漫的约会圣地，同时它也是一个很特别的城镇。
小镇中有很多道路，四通八达。它有 n+1 条的小路为南北方向，有 m+1 条的小路为东西方向，这些道路将 Q 镇划分成了 m×n 个区域，而这些区域，从北到南、从西到东的坐标标识为从坐标 (1,1) 到坐标 (m,n) 。
小W 和小K 在网上找到了情侣们对这m×n个区域的打分 V(i,j)(分数可正可负)。分数越高表示那个区域越适合情侣们出没，越低表示不适合情侣游玩。为了方便游玩，小 W 和小 K 决定选定一个连续的区域集合作为他们的游玩范围。例如，如果他们选择了最西北的区域(m1,n1)和最东南(m2,n2)区域 (m1≤m2，n1≤n2) ，那么他们的活动范围是 {D(i,j)(m1≤i≤m2，n1≤vj≤n2)} ，他们游玩的欢乐值则为这些活动范围的区域评分总和。
小 W 和小 K 希望他们游玩范围内的区域的欢乐值最大。
而身为单身狗的你的任务是编写一个程序，求出他们的活动范围(m1,n1)，(m2,n2)的欢乐值的最大值。

Input

输入第一行为整数 m,n，用空格隔开
接下来有 m 行，每行有 n 列整数，其中第 i 行第 j 列的整数，代表 V(i,j)，一个整数之间用空格隔开。输入数据保证这些整数中，至少存在一个正整数。

Output

输出只有一行，为最高的欢乐值。

Samples

Input

4 5
1 -2 3 -4 5
6 7 8 9 10
-11 12 13 14 -15
16 17 18 19 20

Output

146

Hint

Limitation

对于 100%的数据，1≤N,M≤200 ，且 V(i,j)∈[−200000,200000]。

Source

2018年泉州市信息奥赛网上研训活动

Source

石光中学 2018年泉州复赛模拟提高组 day1.

实际上，最大子矩阵和就是最大子序列和的二维情况。
我们就拿上面的样例来解释：

1 -2 3 -4 5
6 7 8 9 10
-11 12 13 14 -15
16 17 18 19 20

无非就是选择一个矩形让其最大。这时候最好的选择就是降维（把二维变成一维）
那么我们只要压缩掉其中的一维就可以了（行或列），一般来说是压缩行。

怎么压缩?

比如：

1 -2 3 -4 5
6 7 8 9 10

可以压成 7 5 11 5 15（也就是加起来）。
但是你不知道哪几行加起来变成一维再取最大子序列和是最大的就需要枚举。（从第i行到第j行）

直接放代码叭。

AC code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
int a[205][205],at[205];
int f(int a[],int n)
{
	int mx = -9999999,s=0;
	for(int i=1;i<=n;i++)
	{
		s+=a[i];
		if(s > mx)	mx = s;
		if(s<0)	s = 0;
	}
	return mx;
}
int main() 
{
	int m,n,res=-9999999;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
			
	for(int i=1;i<=n;i++)
	{
		memset(at,0,sizeof at);// 每次清空数组
		for(int j=i;j<=n;j++)
		{
			for(int k=1;k<=m;k++)//列
				at[k] += a[j][k];
			
			int mx = f(at,m);
			if(mx > res)	res = mx;
		}
	}
	cout<<res;
	return 0; 
}

用颜色代表选择的行依次是：