108 - Maximum Sum

🌕🌗🌑🌑🌑

# 題目連結

• 題目連結
• Online Judge
• uDebug

# 題目說明

Time limit: 3.000 seconds

# 題目

A problem that is simple to solve in one dimension is often much more difficult to solve in more than one dimension. Consider satisfying a boolean expression in conjunctive normal form in which each conjunct consists of exactly 3 disjuncts. This problem (3-SAT) is NP-complete. The problem 2-SAT is solved quite efficiently, however. In contrast, some problems belong to the same complexity class regardless of the dimensionality of the problem.

Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the subrectangle with the largest sum is referred to as the maximal sub-rectangle.

A sub-rectangle is any contiguous sub-array of size 1 × 1 or greater located within the whole array. As an example, the maximal sub-rectangle of the array:

$$\begin {matrix} 0 & −2 & −7 & 0\\9 & 2 & −6 & 2\\−4 & 1 & −4 & 1\\−1 & 8 & 0 & −2 \end {matrix}$$

is in the lower-left-hand corner:

$$\begin {matrix} 9 & 2\\−4 & 1\\−1 & 8 \end {matrix}$$

and has the sum of 15.

# Input

The input consists of an N × N array of integers.

The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by N^2 integers separated by white-space (newlines and spaces). These N^2 integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). N may be as large as 100 . The numbers in the array will be in the range [−127, 127] .

# Output

The output is the sum of the maximal sub-rectangle.

# Sample Input

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

# Sample Output

15

# 解題技巧

• 利用兩次 dp (Dynamic Programming) 來完成紀錄最大的子矩陣數值總數
  1. 第一個 dp 是用來記錄矩陣從左上角的矩陣開始，並固定開始位置，一路計算子矩陣數值到右下角。
  2. 第二個 dp 是由 Time Complexity O(n^4) 完成的，利用前面計算的陣列，並以下圖的方式解決中間子陣列的數值計算。
     
  • 註：為了計算方便，我們將陣列大小設為 N + 1 避免判斷 i - 1 或 j - 1 小於 0 的可能性。
• 在計算第二個 dp 的時候每個數值來比大小，並記錄最大值，就為答案。

# Solution

import java.util.*;

public class Main{

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        int[][] arr = new int[N + 1][N + 1];

        int max = Integer.MIN_VALUE;

        for(int i = 1; i < N + 1; i++){

            for(int j = 1; j < N + 1; j++){

                int input = sc.nextInt();

                arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + input;

            }

        }

        for(int i = 1; i < N + 1; i++){

            for(int j = 1; j < N + 1; j++){

                for(int x = i; x < N + 1; x++){

                    for(int y = j; y < N + 1; y++){

                        int curr = arr[x][y] - arr[i - 1][y] - arr[x][j - 1] + arr[i - 1][j - 1];

                        max = Math.max(max, curr);

                    }

                }

            }

        }

        System.out.println(max);

        sc.close();

    }

}