备战蓝桥杯 Day7（序列dp）

基本分类

（1）单序列

        a.最大子段和

        b.最长上升子序列LIS

（2）多序列

        a.最长公共子序列

        b.编辑距离

最大子段和

单序列dp一般开一维数组

最大子段和 - 洛谷https://www.luogu.com.cn/problem/P1115

分析：

写出状态和状态转移方程：
        状态 dp[i]--以第i个元素作为结尾的最大子段和
        状态转移方程--dp[i]=max(dp[i-1]+a[i],a[i])

---

a[]   1  2  3  4  5  6  7(下标)
       2 -4  3 -1  2 -4  3（原数据）

dp[] 1  2  3  4  5  6  7（下标）
       2 -2  3  2  4  0  3（以第i个元素作为结尾的最大子段和）
最后遍历pd求出最大值即为最大子段和

代码实现

#include<iostream>
using namespace std;
#include <limits.h>
const int N=2e5+10;
int dp[N];
int a[N];//原始数据
int main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
			cin >> a[i];
	//有的题目需要单独置边界;
	dp[1] = a[1];
	int mx = INT_MIN;//要加头文件#include ＜limits.h＞
	for (int i = 1; i <= n; i++)
	{
		dp[i] = max(dp[i - 1] + a[i], a[i]);
		mx = max(mx, dp[i]);
	}
	cout << mx << endl;
    return 0;
}

1282：最大子矩阵

【题目描述】

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 × 1)子矩阵。

比如，如下4 × 4的矩阵

0  -2 -7  0
9  2 -6  2
-4  1 -4  1
-1  8  0 -2

的最大子矩阵是

 9 2
-4 1
-1 8

这个子矩阵的大小是15。

【输入】

输入是一个N×N�×�的矩阵。输入的第一行给出N(0<N≤100)�(0<�≤100)。再后面的若干行中，依次(首先从左到右给出第一行的N�个整数，再从左到右给出第二行的N�个整数……)给出矩阵中的N2�2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127][−127,127]。

【输出】

输出最大子矩阵的大小。

【输入样例】

4
0 -2 -7  0
9  2 -6  2
-4  1 -4  1
-1  8  0 -2

【输出样例】

15

 思路：压维处理，转变成求某一区间行i1-i2行之间第j列的最大子段和问题

#include<iostream>
using namespace std;
#include <limits.h>
const int N=1e2+10;
int a[N][N];
int dp[N];
int b[N];//压维
int presum[N][N];//presum[i][j]--第j列前i项和
int main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> a[i][j];
			//处理前缀和
			presum[i][j] = presum[i - 1][j] + a[i][j];
		}
	}
	int mx = INT_MIN;
	//第i1行到i2行的最大子段和
	for (int i1 = 1; i1 <= n; i1++)
	{
		for (int i2 = i1; i2 <= n; i2++)
		{
			for (int j = 1; j <= n; j++)
			{
				b[j] = presum[i2][j] - presum[i1 - 1][j];
				//求第j列结尾的最大子段和
				dp[j] = max(dp[j-1]+b[j],b[j]);
				mx = max(mx,dp[j]);
			}
		}
	}
	cout << mx;
    return 0;
}