动态规划——找出最大矩阵和

vlambda
2022-03-11

动态规划——找出最大矩阵和

问题描述

来源：POJ第1050题

难度：中等

给你一个N*N的矩阵，在矩阵中寻找一个h*w的矩阵，使得对于所有可能的矩阵，这个矩阵的所有元素和最大，并输出这个最大值。

示例 1：

输入：
 4
 0 -2 -7  0
 9  2 -6  2
-4  1 -4  1
-1  8  0 -2
输出：15

解释：9 2 -4 1 -1 8这个矩阵的和最大，和为15。

动态规划解决

在选择一个元素a[j]的时候，只有两种情况，将a[i]至a[j-1]加上，或者从a[j]以j为起点开始。用一个数组dp[i]表示以i为结束的最大子段和，对于每一个a[i]，加上dp[i-1]成为子段，或以a[i]开始成为新段的起点。因为只需要记录dp值，所以复杂度是O(n)。

我们再来看下代码

import java.util.Scanner;/** * @author Wanghs * @create 2022/3/10 * @description */public class Main { private static int[][] sum; //s(i,j)代表以第i行第j个元素为起始，垂直长度为row+1的列的和。 private static int[][] arr; //存储二维数组 private static int n; //存储二维数组的边长    private static int totalMax = -12800; //存储最终结果 private static void findMax() { int[] rowP = new int[n]; //动态规划序列 int[] rowA = new int[n]; //放置当前操作行 for (int row = 0; row < n; row++) { for (int i = 0; i < (n - row); i++) { rowA = arr[row + i]; for (int j = 0; j < n; j++) { sum[row][j] += rowA[j]; } rowP[0] = sum[row][0]; //问题转化成，在这个行中，求最大字段和的问题 for (int j = 1; j < n; j++) { //一维最大子序列和的问题 if (rowP[j - 1] < 0) { rowP[j] = sum[row][j]; } else { rowP[j] = rowP[j - 1] + sum[row][j]; } } int max = -12800; for (int j = 0; j < n; j++) { if (rowP[j] > max) { max = rowP[j]; //求出的max就是在垂直长度为row+1的所有矩形中，矩形内元素和的最大值 } } if (totalMax < max) { totalMax = max; //最终结果 } } }    } public static void main(String[] args) { Scanner scan = new Scanner(System.in); n = scan.nextInt(); arr = new int[n][n]; sum = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { arr[i][j] = scan.nextInt(); } } findMax(); System.out.println(totalMax); scan.close(); }}