0032.子矩阵的最大面积.md

32. 子矩阵的最大面积

题目链接

C++

#include <bits/stdc++.h>
using namespace std;
/*
代码在solve函数里面
*/
void solve(){
    int h,w;
    cin >> h >> w;
    int y,x;
    cin >> y;
    int yCut[y];
    for (int i = 0; i < y; ++i) {
        cin >> yCut[i];
    }
    cin >> x;
    int xCut[x];
    for (int i = 0; i < x; ++i) {
        cin >> xCut[i];
    }
    vector<int>Height, Width;
    int pre = 0;
    for (int i = 0; i < y; ++i) {
        Height.push_back(yCut[i]-pre);
        pre = yCut[i];
    }
    Height.push_back(h-pre);
    pre = 0;
    for (int i = 0; i < x; ++i) {
        Width.push_back(xCut[i]-pre);
        pre = xCut[i];
    }
    Width.push_back(w-pre);
    int maxH = *max_element(Height.begin(), Height.end());
    int maxW = *max_element(Width.begin(), Width.end());
    cout << maxH * maxW << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    while (T -- ){
        solve();
    }

    return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;

/*

首先读取输入数据，然后对水平和垂直切割数组进行排序，并利用辅助函数 getMaxInterval 计算每个方向上切割区间的最大值。最终，将两个方向上的最大切割区间相乘即得到最大子矩形的面积。

*/
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取矩形的高度和宽度
        int H = scanner.nextInt();
        int W = scanner.nextInt();

        // 读取yCutting数组的长度和内容
        int yCuttingLength = scanner.nextInt();
        int[] yCutting = new int[yCuttingLength];
        for (int i = 0; i < yCuttingLength; i++) {
            yCutting[i] = scanner.nextInt();
        }

        // 读取xCutting数组的长度和内容
        int xCuttingLength = scanner.nextInt();
        int[] xCutting = new int[xCuttingLength];
        for (int i = 0; i < xCuttingLength; i++) {
            xCutting[i] = scanner.nextInt();
        }

        // 对切割点进行排序
        Arrays.sort(yCutting);
        Arrays.sort(xCutting);

        // 计算水平切割区间的最大值
        int maxHorizontalInterval = getMaxInterval(yCutting, H);

        // 计算垂直切割区间的最大值
        int maxVerticalInterval = getMaxInterval(xCutting, W);

        // 计算最大子矩形的面积
        int maxSubrectangleArea = maxHorizontalInterval * maxVerticalInterval;

        // 输出结果
        System.out.println(maxSubrectangleArea);
    }

    // 辅助函数：计算最大切割区间
    private static int getMaxInterval(int[] cuttingArray, int dimension) {
        int maxInterval = cuttingArray[0];  // 第一个切割区间从边界到第一个切割点的距离
        for (int i = 1; i < cuttingArray.length; i++) {
            maxInterval = Math.max(maxInterval, cuttingArray[i] - cuttingArray[i - 1]);
        }
        maxInterval = Math.max(maxInterval, dimension - cuttingArray[cuttingArray.length - 1]);  // 最后一个切割区间从最后一个切割点到边界的距离
        return maxInterval;
    }
}

Python

Go

JS

C

#include <stdio.h>
#include <stdlib.h>

void solve() {
    int h, w;
    scanf("%d%d", &h, &w);
    int y, x;
    scanf("%d", &y);
    int* yCut = malloc(y * sizeof(int));
    for (int i = 0; i < y; ++i) {
        scanf("%d", &yCut[i]);
    }
    scanf("%d", &x);
    int* xCut = malloc(x * sizeof(int));
    for (int i = 0; i < x; ++i) {
        scanf("%d", &xCut[i]);
    }
    int* Height = malloc((y + 1) * sizeof(int));
    int pre = 0;
    for (int i = 0; i < y; ++i) {
        Height[i] = yCut[i] - pre;
        pre = yCut[i];
    }
    Height[y] = h - pre;
    int* Width = malloc((x + 1) * sizeof(int));
    pre = 0;
    for (int i = 0; i < x; ++i) {
        Width[i] = xCut[i] - pre;
        pre = xCut[i];
    }
    Width[x] = w - pre;
    int maxH = Height[0];
    int maxW = Width[0];
    for (int i = 1; i <= y; ++i) {
        if (Height[i] > maxH) {
            maxH = Height[i];
        }
    }
    for (int i = 1; i <= x; ++i) {
        if (Width[i] > maxW) {
            maxW = Width[i];
        }
    }
    printf("%d\n", maxH * maxW);

    free(yCut);
    free(xCut);
    free(Height);
    free(Width);
}

int main() {
    int T = 1;
    while (T--) {
        solve();
    }

    return 0;
}