最大子区域问题也是笔试面试非常常见的问题，典型的就是数组的最大子串和矩阵的最大子矩阵，一般伴随着求和求积这类操作。
下面我们就来研究一下。
53. Maximum Subarray
题意：
最大子区域问题的最经典类型就是数组的最大子区间和问题
思路：
dp枚举每个位置，动态维护以当前元素为结尾的最大子区间和总最大子区间，转移只需要与前项比较即可
代码：
/*
Author Owen_Q
*/
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int re=0;
int remax = nums[0];
for(int i:nums)
{
re = max(re+i,i);
remax = max(remax,re);
}
return remax;
}
};
152. Maximum Product Subarray
题意：
数组最大子区区间和问题的第一个变种就是数组最大子区间积问题
思路：
同样是数组最大子区间问题，大体思路都是一样的，唯一要解决的问题就是，负数乘法会把原来最小值变为最大值。于是，在原来基础上，同时维护最大值和最小值两个变量即可
代码：
/*
Author Owen_Q
*/
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
vector<int> m1(n);
vector<int> m2(n);
m1[0] = nums[0];
m2[0] = nums[0];
int re = nums[0];
for(int i=1;i<n;i++)
{
if(nums[i]>0)
{
m1[i] = max(nums[i],nums[i]*m1[i-1]);
m2[i] = min(nums[i],nums[i]*m2[i-1]);
}
else
{
m1[i] = max(nums[i],nums[i]*m2[i-1]);
m2[i] = min(nums[i],nums[i]*m1[i-1]);
}
re = max(re,m1[i]);
}
return re;
}
};
To the Max
题意：
数组最大子区区间和问题的另一个变种就是二维矩阵的最大子矩阵和问题
思路：
参考之前求解01矩阵的最大子矩阵和思路（最大01子矩阵问题（单调栈优化）），这题就是个典型的一维向二维扩展延伸问题。
对于一维，我们只需要枚举结束的位置，然后转移最大区间和。
相似的，对于二维，我们可以枚举矩阵的上下边界，然后求和压缩即可转移为一维问题，整体复杂度为
代码：
/*
Author Owen_Q
*/
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
const int maxn = 1e2+7;
int s[maxn];
int a[maxn][maxn];
int main() {
int n;
cin >> n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin >> a[i][j];
int remax = a[0][0];
for(int i=0;i<n;i++)
{
memset(s,0,sizeof s);
for(int j=i;j<n;j++)
{
int re = 0;
for(int k=0;k<n;k++)
{
s[k] += a[j][k];
re = max(s[k],re+s[k]);
remax = max(remax,re);
//cout << i << "*" << j << "*" << k << "*" << re << "*" << remax << endl;
}
}
}
cout << remax << endl;
return 0;
}
