求二维数组的最大子数组的和

 

 

思路：通过降维进行运算，每一行每次进行相同程度的加法运算，然后存到一个数组中就成了一维数组的求最大子数组的和，例如上图先进行[A][3]~[A][5]的求最大子数组的和，然后进行A列和B列相加再求最大子数组的和，如此循环到A+B+......+F，然后再从

B列开始进项如上操作，每一次求出最大子数组的和之后都会和最大值进行比较，然后选出最大值，输出结果。时间复杂度为O(n^4).....想不出来降低时间复杂度的方法。。。

 

 

代码如下

import java.util.Scanner;public class Shuzu{            public static void main(String[] args) {        Scanner sc =new Scanner(System.in);        System.out.println("请输入一个二维数组");        int[][] num = new int[5][5];        int[] num1=new int[5];                int sum=0;        int sum1=0;        int m,n;                for(int i=0;i<5;i++) {            for(int j=0;j<5;j++) {                num[i][j]=sc.nextInt();            }        }        for(int j=0;j<5;j++) {                        for(int a=j;a<5;a++) {                for(int i=0;i<5;i++) {                    num1[i]=0;                    for(int b=0;b<=j;b++) {                        num1[i]=num[i][b]+num1[i];                    }                    for(int q=0;q<5;q++) {                        sum1=num1[q];                        for(int p=q+1;p<5;p++) {                            sum1=sum1+num1[p];                            if(sum1>sum) {                                sum=sum1;                            }                        }                    }                }            }        }                System.out.println("最大子数组的和为："+sum);            }    }

 

运行结果：