首页 > 代码库 > 最大联通子数组求和
最大联通子数组求和
设计题目:求一个二维数组的连通的数组中和最大的最大值。
设计思路:
先建立二维数组并遍历二维数组,将所有的正整数进行分块,然后验证是否联通,如果不联通,则判断路径。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
package demo; import java.util.*; public class Lmax { static Scanner scanner = new Scanner(System.in); public static void main(String args[]){ int m,n; int b; Scanner scanner = new Scanner(System.in); System.out.println( "请输入二维数组的列数:" ); m = scanner.nextInt(); System.out.println( "请输入二维数组的行数:" ); n = scanner.nextInt(); int arr[][] = new int [n][m]; System.out.println( "请输入:" ); for ( int i = 0 ;i<n;i++) for ( int j= 0 ;j<m;j++) { arr[i][j] = scanner.nextInt(); } System.out.println( "\n" ); b = maxArrSum(arr); System.out.println( "最大联通数组和为" +b); } public static int [][] arrSum( int arr[][]){ int m = arr.length; int n = arr[ 0 ].length; int p[][] = new int [m+ 1 ][n+ 1 ]; p[ 0 ][ 0 ] = arr[ 0 ][ 0 ]; for ( int i= 0 ; i<=m; i++) p[i][ 0 ] = 0 ; for ( int i= 0 ; i<=n; i++) p[ 0 ][i] = 0 ; for ( int i= 1 ; i<=m; i++){ for ( int j= 1 ; j<=n; j++){ p[i][j] = p[i- 1 ][j] + p[i][j- 1 ] + arr[i- 1 ][j- 1 ] - p[i- 1 ][j- 1 ]; } } return p; } static int maxArrSum( int arr[][]){ int m = arr.length; int n = arr[ 0 ].length; int p[][] = arrSum(arr); int ans = Integer.MIN_VALUE; for ( int i= 1 ; i<=m; i++){ for ( int j= 1 ; j<=n; j++){ for ( int endi=i; endi <=m; endi++){ for ( int endj=j; endj<=n; endj++){ int sum = p[endi][endj] - p[i- 1 ][endj] - p[endi][j- 1 ] + p[i- 1 ][j- 1 ]; if (ans < sum) ans = sum; } } } } return ans; } } |
截图:
总结:这次实验是我和张家星同学一块努力完成的,其间在弄实现的算法时较为麻烦,但在我们共同努力下通过上几次实验基础还完成了这次实验,对复杂的问题进行简单化,逐步完成。
最大联通子数组求和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。