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

问题描述

来源：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();    }}