package beautyOfCoding;
import java.util.Arrays;
import java.util.Random;
public class MaxSubArraySum2 {
/**
* 编程之美 子数组之和的最大值(二维)
*/
private static final int ROW = 5;
private static final int COL = 6;
private static final int MAX = 127;
private boolean invalidInput = false;
private static int[] source; //[-127,127]共127*2+1个数
static {
int n = MAX * 2 + 1;
source = new int[n];
for (int i = 0; i < n; i++) {
source[i] = i - MAX;
}
}
public static void main(String[] args) {
//生成指定行数和列数的数组。数组元素是[-127,127]范围内的随机数
int[][] B = new int[ROW][COL];
int n = MAX * 2 + 1;
Random random = new Random();
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
int pos = random.nextInt(n);
int num = source[pos];
B[i][j] = num;
}
System.out.println(Arrays.toString(B[i]));
}
/*int[][] B = {
{0, -2, -7, 0},
{9, 2, -6, 2},
{-4, 1, -4, 1},
{-1, 8, 0, -2}
};*/
//方法A-全枚举
MaxSubArraySum2 test = new MaxSubArraySum2();
int max = test.maxSubArraySumA(B);
if (test.invalidInput) {
System.out.println("invalid input");
} else {
System.out.println(max);
}
//方法B-部分和
MaxSubArraySum2 test2 = new MaxSubArraySum2();
int max2 = test2.maxSubArraySumB(B);
if (test2.invalidInput) {
System.out.println("invalid input");
} else {
System.out.println(max2);
}
//方法C-转化为一维
MaxSubArraySum2 test3 = new MaxSubArraySum2();
int max3 = test3.maxSubArraySumB(B);
if (test3.invalidInput) {
System.out.println("invalid input");
} else {
System.out.println(max3);
}
}
/**
* 转化为一维。
*/
public int maxSubArraySumC(int[][] B) {
int max = Integer.MIN_VALUE;
if (B == null) {
invalidInput = true;
} else {
int row = B.length;
for (int a = 0; a < row; a++) {
for (int c = a; c < row; c++) {
int[] BC = this.getBC(B, a, c);
int oneDimension = this.maxInOneDimensionalArray(BC);
if (max < oneDimension) {
max = oneDimension;
}
}
}
}
return max;
}
/**
* maxSubArraySumC的辅助方法。得到第a行到第c行所代表的一维数组
*/
public int[] getBC(int[][] B,int a,int c){
int col=B[0].length;
int[] BC = new int[col];
for(int i=0;i<col;i++){
for(int j=a;j<=c;j++){
BC[i] += B[j][i];
}
}
return BC;
}
//子数组之和的最大值-一维
public int maxInOneDimensionalArray(int[] a){
//略去参数检查
int Start=0;
int All=0;
for(int i=0,len=a.length;i<len;i++){
All=this.maxNum(a[i],Start+a[i],All);
Start=this.maxNum(a[i],a[i]+Start); //if start<0, start=a[i]
}
return All;
}
/**
* 用部分和的形式。其中辅助数组PS额外多一行多一列(默认初始化为0),方便计算“部分和”的“部分和”,需仔细体会
* PS[i][j] 表示元素(1,1)(对应原始数组B的B[0][0])和当前元素(i,j)为顶点对的子矩阵的部分和,部分和的计算如下:
* PS[i][j] = A[i][j]+PS[i-1][j]+PS[i][j-1]-PS[i-1][j-1]
*/
public int maxSubArraySumB(int[][] B) {
int max = Integer.MIN_VALUE;
if (B == null) {
invalidInput = true;
} else {
int row = B.length;
int col = B[0].length;
int[][] PS = new int[row+1][col+1];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
PS[i+1][j+1] = PS[i][j+1] + PS[i+1][j ] - PS[i][j] + B[i][j];
}
}
max = this.maxPSij(PS);
}
return max;
}
/**
* maxSubArraySumB的辅助方法
* 求“部分和”的“部分和”:求得(imin, imax, jmin, jmax)代表的矩形区域的和,即题目所求
*/
public int maxPSij(int[][] PS) {
int max = Integer.MIN_VALUE;
int row = PS.length;
int col = PS[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
for (int m = i; m < row; m++) {
for (int n = j; n < col; n++) {
max = this.maxNum(max, PS[i][j], PS[m][n],
(PS[m][n] - PS[m][j] - PS[i][n] + PS[i][j]));
}
}
}
}
return max;
}
/**
* 穷举法,求部分和也是用枚举,有六个for循环,复杂度相当高,不过可用于检验其他方法是否正确
*/
public int maxSubArraySumA(int[][] B) {
int max = Integer.MIN_VALUE;
if (B == null) {
invalidInput = true;
} else {
int row = B.length;
int col = B[0].length;
for (int imin = 0; imin < row; imin++) {
for (int imax = imin; imax < row; imax++) {
for (int jmin = 0; jmin < col; jmin++) {
for (int jmax = jmin; jmax < col; jmax++) {
int tmpSum = sum(B, imin, imax, jmin, jmax);
if (tmpSum > max) {
max = tmpSum;
}
}
}
}
}
}
return max;
}
/**
* maxSubArraySumA的辅助方法
* 枚举求得(imin, imax, jmin, jmax)代表的矩形区域的和
*/
public int sum(int[][] B, int imin, int imax, int jmin, int jmax) {
int result = 0;
for (int i = imin; i <= imax; i++) {
for (int j = jmin; j <= jmax; j++) {
result += B[i][j];
}
}
return result;
}
/**
* 返回最大的数
*/
public int maxNum(int x, int... yy) {
for (int y : yy) {
if (x < y) {
x = y;
}
}
return x;
}
}
分享到:
相关推荐
有学习C语言的同学可以试试做这个题目,涉及到指针,函数,二维数组的相关知识,里面附带本人自己写的代码(vs2008环境),不足的地方望多提意见。
c语言基础 c语言基础_c语言编程基础之二维数组操作示例_三维形体的表面积
c语言基础 c语言基础_c语言编程基础之二维数组操作_两地调度
c语言基础 c语言基础_c语言编程基础之二维数组操作示例_相对名次
动态二维数组 动态二维数组 动态二维数组
c语言基础 c语言基础_c语言编程基础之二维数组操作示例_图片平滑器
二维数组基本操作的编程实现(2学时,验证型),掌握数组的建立、读取数据、压缩存储等基本操作的编程实现,存储结构可以在顺序结构或链接结构中任选,也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序...
本例利用MFC编程实现二维数组在格网中的显示
c语言基础 c语言基础_c语言编程基础之二维字符串数组示例_Bigtram分词
C++关于信息学竞赛 二维数组23个源文件试题 供初学者练习 #include using namespace std; main() { int a[6][6],max,max_y,min,min_x; for(int i=1;i;i++) for(int j=1;j;j++) cin>>a[i][j]; for(int i...
主要介绍了Java编程一维数组转换成二维数组,分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
可以读取二维数组所有数据,基于LabVIEW编程语言
一些C++关于二维数组的编程实例,可以直接运行
用java实现二维数组的转置,1.输入想要创建的数组的维数M;2.分别输入M行数组元素;3.打印数组;4.数组转置;5.打印转置后的数组
用数组创建函数创建一个二维数组显示件,成员为: 4 5 6 1 2 3 3 4 5 6 1 2 2 3 4 5 6 1 1 2 3 4 5 6 编程将上述创建的数组转置为: 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 1 5 6 1 2 6 1 2 3
2018/06/09 周六 20:31 295 03计算矩阵边缘元素之和.cpp 2018/06/09 周六 21:21 667 04错误探测.cpp 2018/06/09 周六 21:24 870 05计算鞍点.cpp 2018/06/09 周六 21:26 594 06图像相似度.cpp 2018/06/17 周日 14:20 ...
在文件中创建Test2、Exchange、...在Exchange类中编写exchange()方法,在方法中创建两个数组arraryA、arraryB,arraryB[j][i]=arraryA[i][j]实现数组的转置。 在Out类中编写out()方法,在方法中用for循环遍历实现输出
本文实例讲述了PHP实现一维数组与二维数组去重功能。分享给大家供大家参考,具体如下: 数组中重复项的去除 一维数组的重复项: 使用array_unique函数即可,使用实例如下: <?php $aa=array("1","2","3","3","2...
C语言编程技术实践 二维数组教学单元设计.doc 学习资料 复习资料 教学资源
java 二维数组矩阵乘法的实现方法,需要的朋友可以参考一下