关于求已知整数数组的连续子数组的最大和的方法 ——基于一维数组的循环，甚至推广到二维情况上

日期：2019.3.21

博客期：049

星期四

　　先二话不说，先交代码，今天训练的内容是“这个整数数组是允许开头和结尾结合在一起的”，大家的思路都是扩大数组内容，就是将读入的数据存入数组，并将数据量扩大一倍——把开头和结尾相连！

　　我仔细一想这也可以啊！但是当老师讨论到数组位数的时候，他说最多设置位数不超过 2N-1 （N是原数组的位数），这里我想如果取全部的数据该怎么办？

　　实例： 1，2，-3，2，0

　　按照以前的算法应该取得 1，2 ，得到结果 3

　　按照新算法得到 2，0，1，2 ，得到结果 5

　　但是大家说的算法是连接数组，也就是得到新数组 1，2，-3，2，0，1，2，-3，2 ；从而算得结果为 5 ，但是如果全部是正数呢？应该加以判断？

　　实例2：10， -20， 25， -50 ，15

　　得到结果应该是取得 15，10，-20，25 ，得到结果30

　　下边详细介绍一下我的方法：

　　添加前边最大值的记录和前边最小值的记录，其中这个最小值一定是的位数一定要大于取得最大值时的记录，最终计算比 rmax 大的内容—— 总值 - 最小值 + 最大值（得到的这个记录是连同最后一个值和第一个值的最大和）

  1 package pvp;
  2 
  3 import java.io.File;
  4 import java.io.FileNotFoundException;
  5 import java.util.Scanner;
  6 
  7 public class TestPlay4 {
  8     public static void main(String[] args) {
  9         //AddRandomNumber.Renew3();
 10         File f = new File("data/data.txt");
 11         if(!f.exists())
 12         {
 13             System.out.println("文件不存在!");
 14             System.exit(0);
 15         }
 16         //存储导入内容
 17         String str;
 18         //内容
 19         Scanner sc = null;
 20         try {
 21             sc = new Scanner(f);
 22         } catch (FileNotFoundException e1) {
 23             System.out.println("文件不存在!");
 24             System.exit(0);
 25         }
 26         //最大值
 27         int rmax = Integer.MIN_VALUE;
 28         //正数总值
 29         int Tnum = Integer.MIN_VALUE;
 30         //负数总值
 31         int Fnum = 0;
 32         //记录是否发生转变
 33         int sis = 0;
 34         //标记是第几程度
 35         int attitude = 0;
 36         //------------------------<Test4新加内容>
 37         //标记从第1个开始数的最大值
 38         int isState = 0;
 39         //标记从第1个开始数的最小值
 40         int isNotState = 0;
 41         //内容标记
 42         int kort = 0;
 43         //从第1个开始数的最大值的位置
 44         int u_er = 0;
 45         //从第1个开始数的最小值的位置
 46         //int v_er = 0;
 47         //------------------------</Test4新加内容>
 48         //循环
 49         try
 50         {
 51             //--------------------[Test4新加内容]
 52             int p_num = 0;//------[Test4新加内容]
 53             //--------------------[Test4新加内容]
 54             if(!sc.hasNext())
 55             {
 56                 System.out.println("文件内容为空!");
 57                 System.exit(0);
 58             }
 59             while(sc.hasNext())
 60             {
 61                 ++p_num;
 62                 int p;
 63                 str = sc.next();
 64                 p = Integer.parseInt(str);
 65                 if(attitude==0)                    //---------------------------------------[寻找第一个正数]
 66                 {
 67                     if(p<=0)
 68                         ;
 69                     else
 70                     {
 71                         Tnum = p;
 72                         attitude = 1;
 73                     }
 74                 }
 75                 else if(attitude==1)            //---------------------------------------[上一个数为正数]
 76                 {
 77                     if(p<0)
 78                     {
 79                         if(sis==0)
 80                         {
 81                             sis = 1;
 82                             Fnum += p;
 83                         }
 84                         else
 85                             Fnum = p;
 86                         attitude = -1;
 87                     }
 88                     else
 89                         Tnum += p;
 90 
 91                     if(Tnum>rmax)
 92                         rmax = Tnum;
 93                 }
 94                 else                            //---------------------------------------[上一个数为负数]
 95                 {
 96                     if(p>0)
 97                     {
 98                         attitude = 1;
 99                         if(Tnum + Fnum > 0)
100                         {
101                             if(Tnum + Fnum > Integer.MAX_VALUE - p)
102                             {
103                                 System.out.println("统计内容超过最大值!");
104                                 System.exit(0);
105                             }
106                             Tnum = (Tnum + Fnum) + p;
107                         }
108                         else
109                             Tnum = p;
110                     }
111                     else
112                     {
113                         if(Fnum<Integer.MIN_VALUE-p)
114                         {
115                             System.out.println("统计内容超过最小值!");
116                             System.exit(0);
117                         }
118                         Fnum += p;
119                     }
120                 }
121                 if(p>rmax)
122                     rmax = p;
123                 if(Tnum>rmax)
124                     rmax = Tnum;
125                 
126                 kort = kort + p;
127                 
128                 if(isState<kort)
129                 {
130                     isState = kort;
131                     u_er = p_num;
132                 }
133                 if(isNotState>kort&&p_num>=u_er)
134                     isNotState = kort;
135                 else if(p_num<u_er)
136                     isNotState = 0;
137             }
138             //--------------------[Test4新加内容]
139             if(kort-isNotState+isState>rmax)
140                 rmax = kort-isNotState+isState;
141             //--------------------[Test4新加内容]
142         }
143         catch( NumberFormatException e){
144             System.out.println("输入内容不是数字或者过大!");
145             System.exit(0);
146         }
147         System.out.println(rmax);
148         sc.close();
149     }
150 }

TestPlay4.java

　　Part 2:那么，下面就让我们进入第二阶段吧！那就是二维数组阶段！

　　简而言之，就是如图得到和最大的分块！还必须是矩形！

　　呃~想着说一下思路，说一下我是如何从一维数组到二维数组进行转换的：

　　1、一维数组

　　　　计算每一个位置的数组和，利用公式得到每一项的结果，通过最大值减去最小值，最大值位数大于最小值得到部分连续和！

　　2、二维数组

　　　　计算每一个位置的数组和，利用公式得到每一项的结果，通过诱导得到的余角（如图中的3，2，-9，-1，-2，0，2）的和最小值 min，之后用当前的总值减去min得到的值的最大值就是所求的最大值了！

　　　　得到了和数组，如何得到第 k 行，第 l 列的数据到第 i 行，第 j 列的数据和：

　　　　从而根据思路，诱导引出结果：

　　　　图上是到 i = 6, j = 4时，k = 1, l = 3时得到的结果。

　　　　上图中分别有以下含义：

　　　　　　黄色背景区域区域表示 i 和 j 所覆盖的区域。

　　　　　　蓝色字迹所取到的区域是确认是否为最大值的连续子数组区域。

　　　　　　红色字迹的区域是黄色背景区域减去蓝色字迹区域。

　　　　　　我的思想就是通过 i 和 j 的每一次的遍历中，通过红色字迹区域的取得的最小值，和黄色背景区域的固定值做差，找到在蓝色字迹区域的最大值。然后再统计找出每一个 i 和 j 的组合过程中取到的最大值的集合里面的最大值，那就是我们要寻找的结果了！

　　　　实现的初步代码如下：

 1 package pvp;
 2 
 3 import java.io.File;
 4 import java.io.FileNotFoundException;
 5 import java.util.Scanner;
 6 
 7 public class TestPlay5 {
 8     public static void main(String[] args) {
 9         //AddRandomNumber.Renew();
10         File f = new File("data/data2.txt");
11         if(!f.exists())
12         {
13             System.out.println("文件不存在!");
14             System.exit(0);
15         }
16         //存储导入内容
17         String str;
18         //内容
19         Scanner sc = null;
20         try {
21             sc = new Scanner(f);
22         } catch (FileNotFoundException e1) {
23             System.out.println("文件不存在!");
24             System.exit(0);
25         }
26         //最大值
27         int rmax = Integer.MIN_VALUE;
28         //和数组
29         int [][]q;
30         //循环
31         try
32         {
33             if(!sc.hasNext())
34             {
35                 System.out.println("文件内容为空!");
36                 System.exit(0);
37             }
38             int m,n;
39             m = sc.nextInt();
40             q = new int [m][];
41             if(!sc.hasNext())
42             {
43                 System.out.println("文件内容缺少!");
44                 System.exit(0);
45             }
46             n = sc.nextInt();
47             for(int i=0;i<m;++i)
48             {
49                 q[i] = new int [n];
50                 if(!sc.hasNext())
51                 {
52                     System.out.println("文件内容缺少!");
53                     System.exit(0);
54                 }
55                 for(int j=0;j<n;++j)
56                 {
57                     int p;
58                     str = sc.next();
59                     p = Integer.parseInt(str);
60                     
61                     if(i==0)
62                     {
63                         if(j==0)
64                             q[i][j] = p;
65                         else
66                             q[i][j] = q[i][j-1]  + p;
67                     }
68                     else
69                     {
70                         if(j==0)
71                             q[i][j] = q[i-1][j] + p;
72                         else
73                             q[i][j] = q[i][j-1] + q[i-1][j] - q[i-1][j-1] + p;
74                     }
75                     int temp = 0;
76                     for(int k=0;k<i;++k)
77                     {
78                         for(int l=0;l<j;++l)
79                         {
80                             if(temp>=q[i][l]+q[k][j]-q[k][l])
81                                 temp = q[i][l] + q[k][j] - q[k][l];
82                         }
83                     }
84                     if(rmax<q[i][j]-temp)
85                         rmax = q[i][j] - temp;
86                 }
87             }
88         }
89         catch( NumberFormatException e){
90             System.out.println("输入内容不是数字或者过大!");
91             System.exit(0);
92         }
93         System.out.println(rmax);
94         sc.close();
95     }
96 }

TestPlay5.java

　　　　我再次更新一下新的二维数组的代码，多加考虑了总值减去最小值的问题，请以下方代码为准

  1 package pvp;
  2 
  3 import java.io.File;
  4 import java.io.FileNotFoundException;
  5 import java.util.Scanner;
  6 
  7 public class TestPlay6 {
  8     public static void main(String[] args) {
  9         //AddRandomNumber.Renew();
 10         File f = new File("data/data2.txt");
 11         if(!f.exists())
 12         {
 13             System.out.println("文件不存在!");
 14             System.exit(0);
 15         }
 16         //存储导入内容
 17         String str;
 18         //内容
 19         Scanner sc = null;
 20         try {
 21             sc = new Scanner(f);
 22         } catch (FileNotFoundException e1) {
 23             System.out.println("文件不存在!");
 24             System.exit(0);
 25         }
 26         //最大值
 27         int rmax = Integer.MIN_VALUE;
 28         //和数组
 29         int [][]q;
 30         //循环
 31         try
 32         {
 33             if(!sc.hasNext())
 34             {
 35                 System.out.println("文件内容为空!");
 36                 System.exit(0);
 37             }
 38             int m,n;
 39             m = sc.nextInt();
 40             q = new int [m][];
 41             if(!sc.hasNext())
 42             {
 43                 System.out.println("文件内容缺少!");
 44                 System.exit(0);
 45             }
 46             n = sc.nextInt();
 47             for(int i=0;i<m;++i)
 48             {
 49                 q[i] = new int [n];
 50                 if(!sc.hasNext())
 51                 {
 52                     System.out.println("文件内容缺少!");
 53                     System.exit(0);
 54                 }
 55                 for(int j=0;j<n;++j)
 56                 {
 57                     int p;
 58                     str = sc.next();
 59                     p = Integer.parseInt(str);
 60                     
 61                     if(i==0)
 62                     {
 63                         if(j==0)
 64                             q[i][j] = p;
 65                         else
 66                             q[i][j] = q[i][j-1]  + p;
 67                     }
 68                     else
 69                     {
 70                         if(j==0)
 71                             q[i][j] = q[i-1][j] + p;
 72                         else
 73                             q[i][j] = q[i][j-1] + q[i-1][j] - q[i-1][j-1] + p;
 74                     }
 75                     int temp = 0;
 76                     for(int k=-1;k<i;++k)
 77                     {
 78                         for(int l=-1;l<j;++l)
 79                         {
 80                             if(k==-1)
 81                             {
 82                                 if(l==-1)
 83                                 {
 84                                     continue;
 85                                 }
 86                                 else
 87                                 {
 88                                     if(temp>=q[i][l])
 89                                         temp = q[i][l];
 90                                 }
 91                             }
 92                             else
 93                             {
 94                                 if(l==-1)
 95                                 {
 96                                     if(temp>=q[k][j])
 97                                         temp = q[k][j];
 98                                 }
 99                                 else
100                                 {
101                                     if(temp>=q[i][l]+q[k][j]-q[k][l])
102                                         temp = q[i][l] + q[k][j] - q[k][l];
103                                 }
104                             }
105                         }
106                     }
107                     if(rmax<q[i][j]-temp)
108                         rmax = q[i][j] - temp;
109                 }
110             }
111         }
112         catch( NumberFormatException e){
113             System.out.println("输入内容不是数字或者过大!");
114             System.exit(0);
115         }
116         System.out.println(rmax);
117         sc.close();
118     }
119 }

TestPlay6.java