動態(tài)規(guī)劃——找出最大矩陣和

問題描述

來源：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。

動態(tài)規(guī)劃解決

在選擇一個元素a[j]的時候，只有兩種情況，將a[i]至a[j-1]加上，或者從a[j]以j為起點開始。用一個數(shù)組dp[i]表示以i為結(jié)束的最大子段和，對于每一個a[i]，加上dp[i-1]成為子段，或以a[i]開始成為新段的起點。因為只需要記錄dp值，所以復(fù)雜度是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; //存儲二維數(shù)組    private static int n; //存儲二維數(shù)組的邊長????private?static?int?totalMax?=?-12800;?//存儲最終結(jié)果    private static void findMax() {        int[] rowP = new int[n]; //動態(tài)規(guī)劃序列        int[] rowA = new int[n]; //放置當(dāng)前操作行        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];   //問題轉(zhuǎn)化成，在這個行中，求最大字段和的問題                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的所有矩形中，矩形內(nèi)元素和的最大值                    }                }                if (totalMax < max) {                    totalMax = max; //最終結(jié)果                }            }        }????}    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();    }}

你點的每個贊，我都認(rèn)真當(dāng)成了喜歡