动态规划——找出最大矩阵和
问题描述
来源：POJ第1050题
难度：中等
给你一个N*N的矩阵，在矩阵中寻找一个h*w的矩阵，使得对于所有可能的矩阵，这个矩阵的所有元素和最大，并输出这个最大值。
示例 1：
输入：
4
0 -2 -7 09 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();}}
你点的每个赞，我都认真当成了喜欢评论