問(wèn)題描述

來(lái)源：POJ第1050題

難度：中等

給你一個(gè)N*N的矩陣，在矩陣中尋找一個(gè)h*w的矩陣，使得對(duì)于所有可能的矩陣，這個(gè)矩陣的所有元素和最大，并輸出這個(gè)最大值。

示例 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這個(gè)矩陣的和最大，和為15。

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

在選擇一個(gè)元素a[j]的時(shí)候，只有兩種情況，將a[i]至a[j-1]加上，或者從a[j]以j為起點(diǎn)開(kāi)始。用一個(gè)數(shù)組dp[i]表示以i為結(jié)束的最大子段和，對(duì)于每一個(gè)a[i]，加上dp[i-1]成為子段，或以a[i]開(kāi)始成為新段的起點(diǎn)。因?yàn)橹恍枰涗沝p值，所以復(fù)雜度是O(n)。?

我們?cè)賮?lái)看下代碼

import?java.util.Scanner;/** * @author Wanghs * @create 2022/3/10 * @description */public class Main {    private static int[][] sum; //s(i,j)代表以第i行第j個(gè)元素為起始，垂直長(zhǎng)度為row+1的列的和。    private static int[][] arr; //存儲(chǔ)二維數(shù)組    private static int n; //存儲(chǔ)二維數(shù)組的邊長(zhǎng)????private?static?int?totalMax?=?-12800;?//存儲(chǔ)最終結(jié)果    private static void findMax() {        int[] rowP = new int[n]; //動(dòng)態(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];   //問(wèn)題轉(zhuǎn)化成，在這個(gè)行中，求最大字段和的問(wèn)題                for (int j = 1; j < n; j++) {    //一維最大子序列和的問(wèn)題                    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就是在垂直長(zhǎng)度為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();    }}

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