求数组的子数组之和的最大值IV

在之前的基础上又安排了二维数组的，在课上一开始是理解错要求了，简单的以为用循环数组就能解决，但是却忽视了子数组是否能构成矩形，之后课下和同学们讨论，主要是多重遍历，但是我还是没搞明白怎么构成新的二维数组，之后同学给了一段源代码，自己还在摸索：

  1 package b;

  2

  3 import java.util.Scanner;

  4

  5 import javax.print.attribute.standard.PrinterLocation;

  6

  7 public class b

  8 {

  9     public static void main(String[] args)

 10     {

 11         Scanner scanner=new Scanner(System.in);

 12         System.out.println("请输入二维数组的行和列：");

 13         int hang=scanner.nextInt();

 14         int lie=scanner.nextInt();

 15         System.out.println("请输入二维数组：");

 16         int[][] shuzu=new int[hang][lie];

 17

 18         int i,j;

 19         for(i=0;i<hang;i++)

 20         {

 21             for(j=0;j<lie;j++)

 22             {

 23                 shuzu[i][j]=scanner.nextInt();

 24             }

 25         }

 26

 27         System.out.println("此数组中连续和的最大值为："+max(shuzu,hang,lie));

 28

 29     }

 30

 31     static int max(int shuzu[][],int hang,int lie)

 32     {

 33         int max=0,sum=0;

 34         int i,j;

 35         int[] b=new int[lie];

 36         int[] up=new int[hang];

 37         int[] down=new int[hang];

 38         int[] t=new int[hang];

 39         if(lie==1)

 40         {

 41             for (i=0;i<hang;i++)

 42             {

 43                 sum+=shuzu[i][0];

 44                 if(sum<0)

 45                 {

 46                     sum=0;

 47                 }

 48                 if(sum>max)

 49                 {

 50                     max=sum;

 51                 }

 52             }

 53

 54            if(max==0)

 55            {

 56                for(i=0;i<hang;i++)

 57                {

 58                    if(i==0)

 59                    {

 60                        max=shuzu[i][0];

 61                    }

 62                    if(shuzu[i][0]>max)

 63                    {

 64                        max=shuzu[i][0];

 65                    }

 66                }

 67             }

 68         }

 69         else

 70         {

 71             for(i=0;i<hang;i++)

 72             {

 73                 for(j=0;j<lie;j++)

 74                 {

 75                     b[j]=shuzu[i][j];

 76                 }

 77                 int[] c=new int[100];

 78                 c[0]=0;

 79                 int sum1=0,max1=0,k;

 80                 for(k=0;k<lie;k++)

 81                 {

 82                     if(sum1<0)

 83                     {

 84                         sum1=b[k];

 85                     }

 86                     else

 87                     {

 88                         sum1=sum1+b[k];

 89                     }

 90                     c[k]=sum1;

 91                 }

 92                 max1=c[0];

 93                 int mmark=0,smark=0;

 94                 for(k=0;k<lie;k++)

 95                 {

 96                     if (max1<c[k])

 97                     {

 98                         max1= c[k];

 99                         mmark = k;

100                     }

101                 }

102                 for (k = mmark;k >= 0;k--)

103                 {

104                     if (c[k] == b[k])

105                     {

106                         smark = k;

107                         break;

108                     }

109                 }

110                 sum=max1;

111

112                 up[i]=smark;

113                 down[i]=mmark;

114                 t[i]=sum;

115

116             }

117             int t2=t[0];

118             for(i=0;i<hang-1;i++)

119             {

120                 if(up[i]<=down[i+1] && down[i]>=up[i+1])

121                 {

122                     t2+=t[i+1];

123                 }

124                 for(j=up[i];j<up[i+1];j++)

125                 {

126                     if(shuzu[i+1][j]>0) t2+=shuzu[i+1][j];                   //判别独立正数

127                 }

128

129             }

130             max=t2;

131         }

132         return max;

133     }

134 }

巴特西

求数组的子数组之和的最大值IV

最新文章

热门文章