队友~~高雪彤
一、题目:
输入一个二维整形数组,数组里有正数也有负数。
求所有子数组的和的最大值。
二、程序设计思路:
1.先找出二维数组中不包含负数的直接相邻(上下左右相邻)的正整数块。如下图
2.然后转化建模,将该“二维表”与“图”转化,转化方法如下:将每个正整数块看做一个“正元素,将每一个负数看做一个“负元素”,将每一个“正元素”和每一个“负元素”分别作为“图”的结点,其中每个正整数块的和的相反数作为相应“正元素”结点的权值,每个负数的值的相反数作为“负元素”结点的权值,具有直接相邻关系的表中元素,具有双向连通性,结点A与结点B的权值的和定义为从结点A到结点B的“代价”,则该题求最大连通子数组的问题成功转化为求图中的最短路径问题,用弗洛伊德算法可以求出图中每对结点之间的最短路径,遍历求出其中的“代价”最小的一组,再还原出其最短路径,即可找出最大连通子图。
三、源程序代码
package tt20170227; import java.util.ArrayList; public class lala { static int sum; public static void main(String[] args) { // TODO Auto-generated method stub System.out.print(la333()); } public static int la333() { int[][] a = { { -8, 9, 2, 6 }, { -5, 8, 6, -9 }, { 6, 1, 6, 7 } }; int[][] b = new int[3][4]; // 判断连通性,0为未选中,1为选中,2为连通 boolean flag = true; int sum = 0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 4; j++) { b[i][j]=0; System.out.print(a[i][j] + " "); if (a[i][j] >= 0) { b[i][j] = 1; } } System.out.println(" "); } for (int i = 0; i < 3; i++) { for (int j = 0; j < 4; j++) { if (b[i][j] == 1) { switch(i){ case 0: { switch(j){ case 0: { if (a[i + 1][j] + a[i][j] > 0 && b[i + 1][j] == 0) { b[i + 1][j] = 2; } if (a[i][j + 1] + a[i][j] > 0 && b[i][j + 1] == 0) { b[i][j + 1] = 2; } break; } case 3: { if (a[i + 1][j] + a[i][j] > 0 && b[i + 1][j] == 0) { b[i + 1][j] = 2; } if (a[i][j - 1] + a[i][j] > 0 && b[i][j - 1] == 0) { b[i][j - 1] = 2; } break; } default: { if (a[i + 1][j] + a[i][j] > 0 && b[i + 1][j] == 0) { b[i + 1][j] = 2; } if (a[i][j - 1] + a[i][j] > 0 && b[i][j - 1] == 0) { b[i][j - 1] = 2; } if (a[i][j + 1] + a[i][j] > 0 && b[i][j + 1] == 0) { b[i][j + 1] = 2; } break; } } break; } case 2: { switch(j){ case 0: { if (a[i - 1][j] + a[i][j] > 0 && b[i - 1][j] == 0) { b[i - 1][j] = 2; } if (a[i][j + 1] + a[i][j] > 0 && b[i][j + 1] == 0) { b[i][j + 1] = 2; } break; } case 3: { if (a[i - 1][j] + a[i][j] > 0 && b[i - 1][j] == 0) { b[i - 1][j] = 2; } if (a[i][j - 1] + a[i][j] > 0 && b[i][j - 1] == 0) { b[i][j - 1] = 2; } break; } default: { if (a[i - 1][j] + a[i][j] > 0 && b[i - 1][j] == 0) { b[i - 1][j] = 2; } if (a[i][j - 1] + a[i][j] > 0 && b[i][j - 1] == 0) { b[i][j - 1] = 2; } if (a[i][j + 1] + a[i][j] > 0 && b[i][j + 1] == 0) { b[i][j + 1] = 2; } break; } } break; } default: { switch(j){ case 0: { if (a[i + 1][j] + a[i][j] > 0 && b[i + 1][j] == 0) { b[i + 1][j] = 2; } if (a[i - 1][j] + a[i][j] > 0 && b[i - 1][j] == 0) { b[i - 1][j] = 2; } if (a[i][j + 1] + a[i][j] > 0 && b[i][j + 1] == 0) { b[i][j + 1] = 2; } break; } case 3: { if (a[i + 1][j] + a[i][j] > 0 && b[i + 1][j] == 0) { b[i + 1][j] = 2; } if (a[i - 1][j] + a[i][j] > 0 && b[i - 1][j] == 0) { b[i - 1][j] = 2; } if (a[i][j - 1] + a[i][j] > 0 && b[i][j - 1] == 0) { b[i][j - 1] = 2; } break; } default: { if (a[i + 1][j] + a[i][j] > 0 && b[i + 1][j] == 0) { b[i + 1][j] = 2; } if (a[i - 1][j] + a[i][j] > 0 && b[i - 1][j] == 0) { b[i - 1][j] = 2; } if (a[i][j - 1] + a[i][j] > 0 && b[i][j - 1] == 0) { b[i][j - 1] = 2; } if (a[i][j + 1] + a[i][j] > 0 && b[i][j + 1] == 0) { b[i][j + 1] = 2; } break; } } break; } } } System.out.println(a[i][j]); } } for (int i = 0; i < 3; i++) { for (int j = 0; j < 4; j++) { flag = false; if (b[i][j] != 0 && a[i][j] < 0) { b[i][j] = 0; for (int k = 0; k < 3; k++) { for (int q = 0; q < 4; q++) { if (b[k][q] != 0) { if ((b[k + 1][q] <= 0 || b[k + 1][q] > 2) && (b[k - 1][q] <= 0 || b[k - 1][q] > 2) && (b[k][q + 1] <= 0 || b[k][q + 1] > 2) && (b[k][q - 1] <= 0 || b[k][q - 1] > 2)) { flag = true; } } } } if (flag) { b[i][j] = 2; } } } } for (int i = 0; i < 3; i++) { for (int j = 0; j < 4; j++) { if (b[i][j] != 0) { System.out.print(a[i][j] + " "); sum += a[i][j]; } } System.out.println(" "); } return sum; } }
四、总结:
思路是有的,可是有些还是没有办法具体实现,在课下会多思考,争取实现。