二维数组求最大子数组

 1 package shuzu;
 2  
 3 import java.util.*;
 4  
 5 public class shuzu {
 6     static Scanner scanner = new Scanner(System.in);
 7     public static void main(String args[]){
 8         int m,n;
 9         int b;
10         Scanner scanner = new Scanner(System.in);
11         System.out.println("二维数组的列数：");
12         m = scanner.nextInt();
13         System.out.println("二维数组的行数：");
14         n = scanner.nextInt();
15         int arr[][] = new int[n][m];
16         System.out.println("请输入二位数组：");
17         for(int i = 0;i<n;i++)
18             for(int j=0;j<m;j++)
19             {
20                 arr[i][j] = scanner.nextInt();
21                 }
22         System.out.println("
");
23         b = maxArrSum(arr);
24         System.out.println("最大子数组的最大和为"+b);
25         }
26      
27     public static int[][] arrSum(int arr[][]){
28         int m = arr.length;
29         int n = arr[0].length;
30         int p[][] = new int[m+1][n+1];
31         p[0][0] = arr[0][0];
32         for(int i=0; i<=m; i++) p[i][0] = 0;
33         for(int i=0; i<=n; i++) p[0][i] = 0;
34         for(int i=1; i<=m; i++)
35         {
36             for(int j=1; j<=n; j++){
37                 p[i][j] = p[i-1][j] + p[i][j-1] + arr[i-1][j-1] - p[i-1][j-1];
38                 }
39             }
40         return p;
41         }
42  
43     //遍历所有二维数组的矩形区域
44         static int  maxArrSum(int arr[][]){
45         int m = arr.length;
46         int n = arr[0].length;
47         int p[][] = arrSum(arr);
48         int ans = Integer.MIN_VALUE;
49         for(int i=1; i<=m; i++)
50         {
51             for(int j=1; j<=n; j++)
52             {
53                 for(int endi=i; endi <=m; endi++)
54                 {
55                     for(int endj=j; endj<=n; endj++)
56                     {  
57                         int sum = p[endi][endj] - p[i-1][endj] - p[endi][j-1] + p[i-1][j-1];
58                         if(ans < sum) ans = sum;   
59                     }
60                 }   
61             }   
62         }   
63         return ans;   
64     }    
65 }
二维数组
用的是最笨的方法，一个个去比较。
思路分步解析：
1.每个二维矩阵的子数组看作一个小矩阵，
2.将所有的矩阵的之和都求出来
3.遍历比较。