题目:返回一个二维数组中最大子数组的和
要求:
- 输入一个二维数组,数组中有正数也有负数。
- 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
- 求所有子数组的和的最大值
设计思路:
将二维数组分解为若干个一维数组,利用对一维数组求和的方法,求出二维子数组,通过比较选出最大的子数组
源代码:
package erwei; /* * 求二维数组最大子数组的和*/ import java.util.Scanner; public class Shuzutwo { static Scanner in = new Scanner(System.in); public static void main(String[] args) { // TODO 自动生成的方法存根 int row; int clo; int a[] = new int [100]; //定义一个一维数组 int[][] b = new int[20][20]; //输入的二维数组 int value = 0; System.out.println("输入数组的行和列"); row = in.nextInt(); clo = in.nextInt(); System.out.println("输入数组元素"); for(int i = 0; i < row; i++) { for(int j = 0; j < clo; j++) { b[i][j] = in.nextInt(); } } int max = 0; for(int i = 0 ; i < clo ; i++) { a[i] = b[0][i]; } max = maxsum(a); for(int i1 = 0 ; i1 < row-1 ; i1++) { for(int j1 = 0 ; j1 < clo; j1++) // 每一次对一维数组附初值为开始第一行的值 { a[j1] = b[i1][j1]; } for(int j2 = i1+1 ; j2 < row ; j2++) { for(int t = 0; t < clo ; t++) { a[t] = a[t] + b[j2][t]; // 从第j2行开始一直加到最后一行构成一个一维数组 } value = maxsum(a); //调用方法求一维数组的最大子数组 if (value > max) { max = value; } } } for(int i = 0 ; i < clo ; i++) // 计算最后一行的自大子数组 { a[i] = b[row-1][i]; } value = maxsum(a); // 求最后一行的最大子数组 if (value > max) { max = value; } System.out.println("最大子数组为" + max); } //一维数组的最大子数组 public static int maxsum(int a[]) { int sum = a[0]; int value = 0; for(int i = 0; i < a.length; i++) { if (value <= 0) { value = a[i]; }else { value += a[i]; //当value的值仍大于0时就继续相加 } if (sum < value) { sum = value; } } return sum; } }
运行结果: