I 时空的交织

题目描述

小红拿到了一个n行m列的矩阵，矩阵中每个元素的权值由a数组和b数组决定。第i行第j列的元素为ai∗bj。小红希望选择一个子矩形，使得该子矩形所有元素的和尽可能大。你能帮帮她吗？

考察基本知识点:dp查找数组中一段子数组的和的最大最小值
需要思维转换一下的地方(本题关键）:(i1，j1)与(i2,j2)两点围成的矩形中元素的和实际上就是(a[i1]+...+a[i2])*(b[j1]+...b[j2])

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;
int a[N],b[N];


long long find_max(int c[],int num)//dp找区间和的最大值
{
    long long cur=0,res=-2e9;
    for(int i=1;i<=num;i++)
    {
        if(cur>0)cur+=c[i];
        else cur=c[i];
        res=max(res,cur);
    }
    return res;
}

long long find_min(int c[],int num)//dp找区间和的最小值
{
    long long cur=0,res=2e9;
    for(int i=1;i<=num;i++)
    {
        if(cur<0)cur+=c[i];
        else cur=c[i];
        res=min(res,cur);
    }
    return res;
}

int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    
    long long max_a=find_max(a,n);
    long long min_a=find_min(a,n);
    long long max_b=find_max(b,m);
    long long min_b=find_min(b,m);
        
    long long result=max({max_a*max_b,min_a*min_b,max_a*min_b,min_a*max_b});
    
    cout<<result;
    
    return 0;
}