二维前缀和

最大子矩阵和

题目描述

    给定m×n矩阵，找出元素和最大的子矩阵
    输入：
    [-1,2,-1]
    [3,4,5]
    [-2,-3,-4]
    输出：子矩阵[[3,4，5]]，和为12

    解法思路：
    构建二维前缀和数组
    四重循环枚举所有可能的矩形区域：
    前两重循环枚举上下边界
    后两重循环使用类似最大子数组和的Kadane算法优化

#include<iostream>
using namespace std;
int main()
{int n,m;int a[110][110];int p[110][110];cin>>n>>m;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){cin>>a[i][j];}}for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){p[i][j] = a[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];}}for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){cout<<p[i][j]<<" ";}cout<<endl;}int ma = 0;for(int sx = 0;sx<n;sx++){for(int sy = 0;sy<m;sy++){for(int ex = sx;ex<n;ex++){for(int ey = sy;ey<n;ey++){int sum = p[sx][sy] + p[ex+1][ey+1] - p[sx][ey] - p[ex+1][sy];ma = max(ma,sum);}}}}cout<<ma;return 0;
}

和的绝对值不超过K的最长子数组

题目描述

给定一个整数数组nums和一个整数K，请找出该数组中最长的连续子数组，使得该子数组的和的绝对值不超过K。
返回这个子数组的长度。

示例1：
输入：nums=[1,-1,5,-2,3],K=3
输出：4
解释：子数组[1，-1，5，-2]的和为3，绝对值为3，符合条件，长度为4。

示例2：
输入：nums=[-2,-1,2,1]K=1
输出：2
解释：子数组[-1，2]的和为1，绝对值为1，符合条件，长度为2。

#include<iostream>
using namespace std;
int main()
{int n;int a[10000];int p[10000];cin>>n;for(int i = 0;i<n;i++){cin>>a[i];}p[0] = 0;for(int i = 1;i<=n;i++){p[i] = p[i-1] + a[i-1];}int k;cin>>k;int pot = 0;int potw = 0;for(int i = 0;i<n;i++){if(a[i]==k){potw = i;pot = p[i];}}if(pot>=0) cout<<potw; return 0;
}