京东的一道面试题。没答出来，求各位指教【Java】。

原题：
         给定一个数组 int[] num = {-1,2,7,-9,3,6,8,2,-10};【数组不是固定的，是任意数组这只是个例子】
要求：
         将数组中任意连续的项求和的最大值，并输出新的数组。
         举例：3+6+8+2 = 19，在没有任何连续的想加大于19，所以输出 [3,6,8,2]，最大和：19 。
请用Java输出。

32 个解决方案

#1

不考虑性能，如果9个数  分9次   第一次 算  一个区间的最大值 1 2 3 4 5 6 7 8 9
第二次  12 23 34 45 56
。
。
。
。
这样不就ok

#2

暴力计算所有可能情况的和放到map（连续项计算出的和，连续项）。。。然后比较map的key的最大值
坐等好算法

#3

暴力计算效率太低了吧，坐等好算法

#4

这循环次数太多了，坐等大神好算法

#5

想起了  “ 数据结构与算法分析 java ”   里面有这个问题的详解 ，可是我都忘了   

#6

引用 5 楼 o0sxdo0 的回复:

想起了  “ 数据结构与算法分析 java ”   里面有这个问题的详解 ，可是我都忘了   

重新再学习一次

#7

public static int max(int x, int y){
    	return x>y?x:y;
    }

    public static int maxAdd(int a[], int n){
    	int sumV,maxV;
    	sumV = maxV = a[n-1];
    	for(int i = n-2; i>=0; i--){
    		sumV = max(a[i],a[i] + sumV);
    		maxV = max(sumV,maxV);
    	}
    	return maxV;
    }

但是这个只能计算最大连续的和，却无法统计出连续的数组，希望大神给算法

#8

该回复于2017-05-12 09:49:58被管理员删除

#9

个人感觉：两层循环，外层循环是数组，内层循环是从外层选中数组的下标开始往后挨个加，每加上一个数就跟前一个数比较，如果大就保留，如果小就舍弃，内层循环结束后，把这个循环得出的最大数放到list里面，然后等外层循环结束后把list排个序就OK了，这样可能好点吧。

#10

我的思路是先算出每项叠加的和，如int num[] ={-1,2,7,-9,3,6,8,2,-10} 算出int count[]={-1,1,8,-1,2,8,16,18,8}，
然后先判断最大值得出下标，再由单调性得到下标界限，进而得出所要的数组，（ 注意的是当出现多个相同最大值情况的判断）
代码只是为了体现思路，关于内存方面并没有做优化，不喜别看- -，然后代码我就不写注释了，思路同上

public class Main {
	  public static void main(String args[]) {
		  int[] num = {-1,2,7,-9,3,6,8,2,-10};
		  newArrays(num);
	  }
	  
	  private static void newArrays(int [] num){
		  boolean flag = false;
		  int count = 0,max_count=0;
		  int max = 0;
		  int addnum[] = new int [num.length];
		  //算出每项叠加的值
		  for(int i=0;i<num.length;i++){
			  count=count+num[i];
			  addnum[i]=count;
			  //当两个最大值之间没有小于0的值时，max_count并不增加
			  if(addnum[i]<=0){
				  flag=true;
			  }
			  if(max<count){
				  max=count;
				  max_count=1;
				  flag=false;
			  }else if(max==count&&flag==true){
				  max_count++;
			  }
			 //System.out.print(count+ ",");
		  }
		  
		  //max为最大值，max_count是最大值出现的次数，
		  int rel[][] = new int [max_count][num.length];
		  int rel_index = 0;
		  int rel_index_index = 0;
		  int rel_len = num.length+1;//当有多个最大值时出现多个数组，为了判断哪个数组的长度最小用到的标志
		  int result = 0;
		  //System.out.println();
		  //System.out.println("max_count="+max_count);
		  for(int i=0;max_count>0;i++){
			 if(addnum[i]==max){
				 rel[rel_index][rel_index_index++]=num[i];
				 jj:for(int j=i-1;j>=0;j--){
					if(addnum[j]>0){
						rel[rel_index][rel_index_index++]=num[j];
					}else{
						if(rel_index_index<rel_len){
							result=rel_index;
						}
						rel_index++;
						rel_index_index=0;
						max_count--;
						break jj;
					}  
				 }
			  }
		  }
		  //打印
		  StringBuffer sb = new StringBuffer();
		  boolean b = false;
		  for(int i=rel[result].length-1;i>=0;i--){
			  if(rel[result][i]!=0){
				  b=true;
			  }
			  if(b==true){
				  sb.append(rel[result][i]).append(" ");
			  }
		  }
		  System.out.println(sb.toString());
	  
	  }
}
//最后检查的时候发现，我这里并没有对出现多次max后多个最终数组的长度刚好相同的情况，我懒就不加了
//另外个人水平有限，有不对的地方欢迎各位指出

#11

该回复于2017-05-12 16:38:46被管理员删除

#12

用js写了一下,反正java的数据处理也是一样的
  var arr = [4, -5, 20, 7, -9, 3, 6, 8, 2, -80, 99];
    console.log(maxArr(arr));
    function maxArr(arr) {
        var sum; //最大值
        var count; //相加和
        var begInd = 0;//起始下标
        var endInd = 0;//结束下标
        var list = new Array();
        sum = count = arr[0];
        for (var i = 1; i < arr.length; i++) {
            if (count <= 0) {
                count = arr[i];
                begInd = i;
            } else {
                count += arr[i];

            }
            if (count > sum) {
                endInd = i;
                sum = count;

            }
        }
        console.log(sum, begInd, endInd);
        for (var i = begInd; i < endInd + 1; i++) {
            list.push(arr[i]);
        }
        return list;
    }

#13

引用 12 楼 kwgm2015 的回复:

用js写了一下,反正java的数据处理也是一样的
  var arr = [4, -5, 20, 7, -9, 3, 6, 8, 2, -80, 99];
    console.log(maxArr(arr));
    function maxArr(arr) {
        var sum; //最大值
        var count; //相加和
        var begInd = 0;//起始下标
        var endInd = 0;//结束下标
        var list = new Array();
        sum = count = arr[0];
        for (var i = 1; i < arr.length; i++) {
            if (count <= 0) {
                count = arr[i];
                begInd = i;
            } else {
                count += arr[i];

            }
            if (count > sum) {
                endInd = i;
                sum = count;

            }
        }
        console.log(sum, begInd, endInd);
        for (var i = begInd; i < endInd + 1; i++) {
            list.push(arr[i]);
        }
        return list;
    }

如果我没有猜错(js不熟)，你用这串数据试试{-1,101,-50,-51,2,7,-2,3,6,8,4,-28,100}，我觉得会错

#14

引用 13 楼 ITjavaman 的回复:

Quote: 引用 12 楼 kwgm2015 的回复:

用js写了一下,反正java的数据处理也是一样的
  var arr = [4, -5, 20, 7, -9, 3, 6, 8, 2, -80, 99];
    console.log(maxArr(arr));
    function maxArr(arr) {
        var sum; //最大值
        var count; //相加和
        var begInd = 0;//起始下标
        var endInd = 0;//结束下标
        var list = new Array();
        sum = count = arr[0];
        for (var i = 1; i < arr.length; i++) {
            if (count <= 0) {
                count = arr[i];
                begInd = i;
            } else {
                count += arr[i];

            }
            if (count > sum) {
                endInd = i;
                sum = count;

            }
        }
        console.log(sum, begInd, endInd);
        for (var i = begInd; i < endInd + 1; i++) {
            list.push(arr[i]);
        }
        return list;
    }

如果我没有猜错(js不熟)，你用这串数据试试{-1,101,-50,-51,2,7,-2,3,6,8,4,-28,100}，我觉得会错

 
嗯,多谢,确实,前面要加上一个判断,判断begind和endind

#15

如果数组是int[] num = {-1,2,7,-9,3,6,8,2,-10};
那么输出的应该是
     [2, 7, -9, 3, 6, 8, 2]
     [3, 6, 8, 2]

  import java.util.*;

public class Demo {
    public static void main(String[] args) {
        int[] arry = {-1, 2, 7, -9, 3, 6, 8, 2, -10};
        List<int[]> array = getNewArray(arry);
        array.forEach(a -> System.out.println(Arrays.toString(a)));
    }

    /**
     * 现在有一个数组[a0,a1,a2,a3,a4],先求数组中任意连续项之和,并且记住相关的下标.以这个和为key,下标相关的字符串为value放入map中
     * 那么key值最大的下标字符串就是需要的下标
     */
    private static List<int[]> getNewArray(int[] arry) {
        if (arry == null || arry.length == 0) {
            return new ArrayList<>();
        }

        //key是数组任意连续项之和,value为相家项的下标字符串,中间以逗号相隔
        List<Map<Integer, String>> flagList = new ArrayList<>();

        int oldArryLength = arry.length;

        for (int i = 0; i < oldArryLength; i++) {
            for (int j = oldArryLength - 1; j > i; j--) {

                /**
                 * 数组为[a0,a1,a2,a3,a4],oldArryLength=5
                 * 当i=0,j=4的时候,计算a0+...+a4的和作为key,value为 "0,1,2,3,4"
                 * 当I=0,j=3的时候,计算a0+...+a3的和作为key,value为 "0,1,2,3"
                 */
                Map<Integer, String> tempMap = getTempMap(i, j, arry);
                /**
                 * 将上面方法返回的tempMap放到flagList中
                 * flagList只存放key值最大的map,假设有多个map的key值相同,那么flagList的长度就大于1
                 */
                putIntoFlagList(tempMap, flagList);
            }
        }

        return getMaxSumArray(flagList, arry);
    }

    private static List<int[]> getMaxSumArray(List<Map<Integer, String>> flagList, int[] arry) {
        List<int[]> list = new ArrayList<>();
        for (Map<Integer, String> map :
                flagList) {
            String indexStr = "";
            for (Integer key : map.keySet()) {
                indexStr = map.get(key);
            }
            //生成int[]
            //获取第一个下标
            int firstIndex = Integer.parseInt(indexStr.substring(0, indexStr.indexOf(",")));
            //获取最后一个下标
            int lastIndex = Integer.parseInt(indexStr.substring(indexStr.lastIndexOf(",") + 1));
            int[] newArry = Arrays.copyOfRange(arry, firstIndex, lastIndex + 1);
            list.add(newArry);
        }
        return list;
    }

    private static void putIntoFlagList(Map<Integer, String> tempMap, List<Map<Integer, String>> flagList) {
        if (flagList.size() == 0) {
            flagList.add(tempMap);
        } else {
            Integer tempKey = null;
            for (Map.Entry<Integer, String> integerStringEntry : tempMap.entrySet()) {
                tempKey = integerStringEntry.getKey();
            }

            Integer listKey = null;
            Map<Integer, String> firstMap = flagList.get(0);
            for (Map.Entry<Integer, String> integerStringEntry : firstMap.entrySet()) {
                listKey = integerStringEntry.getKey();
            }

            if (tempKey.intValue() > listKey.intValue()) {
                flagList.clear();
                flagList.add(tempMap);
            }

            if (tempKey.intValue() == listKey.intValue()) {
                flagList.add(tempMap);
            }
        }
    }

    private static Map<Integer, String> getTempMap(int i, int j, int[] arry) {
        Map<Integer, String> map = new HashMap<>();

        int sum = 0;
        String indexStr = "";

        for (int k = i; k <= j; k++) {
            sum += arry[k];
            indexStr += k + ",";
        }

        //将indexStr 最后的 ","去掉
        indexStr = indexStr.substring(0, indexStr.lastIndexOf(","));

        map.put(sum, indexStr);
        return map;
    }
}

#16

def contiMax(num):
    ls = [[[i],n] for (i,n) in enumerate(num)]
    ls1 = []

    for l in ls:
        if l[1] > 0:
            if len(ls1)>0:
                if ls1[-1][1] < 0:
                    ls1.append(l)
                else:
                    ls1[-1][1] += l[1]
                    ls1[-1][0] += l[0]
        elif l[1] < 0:
            ls1.append(l)

    def loop(ls):
        ls1 = []
        for l in ls:
            merged = False
            if l[1] > 0:
                if len(ls1) >= 2:
                    agg = [[],0]
                    agg[1] += l[1]
                    agg[0] += l[0]
                    posi = -1
                    for z in range(len(ls1)):
                        j = len(ls1)-1-z
                        agg[1] += ls1[j][1]
                        agg[0] += ls1[j][0]
                        if ls1[j][1] > 0:
                            posi = ls1[j][1]
                            break
                    agg[0].sort()
                    if posi>0 and agg[1] > l[1] and agg[1] > posi:
                        ls1 = ls1[:-(z+1)]
                        ls1.append(agg)
                        merged = True
            if not merged:
                ls1.append(l)
        return ls1

    while True:
        loopedLs = loop(ls1)
        if loopedLs == ls1:
            break
        else:
            ls1 = loopedLs
    max = [[],0]
    for l in ls1:
        if l[1] > max[1]:
            max = l
    return max


if __name__ == "__main__":
    print(contiMax([-1,101,-50,-51,2,7,-2,3,6,8,4,-28,100]))  #output:[[1], 101]
    print(contiMax([-1,2,7,-9,3,6,8,2,-10])) #output:[[4, 5, 6, 7], 19]
    print(contiMax([-3, 12, -7, -9, 42, 26, -8, -50, 60])) #output:[[4, 5, 6, 7, 8], 70]

大体思路：
step 1）合并原始数组中相邻的正数
step 2)  对于 正负(负数有1+个）正 pattern，如果其和大于pattern内任一个正数，则合并
重复step 2，直到数组不再发生变化

#17

简单写了一个,没考虑性能,结果也只取了一组.
 

public static void main(String[] args) {
        int[] num = {-1,2,7,-9,3,6,8,2,-10};
        int[] re = max(num);
        for(int r : re){
            System.out.println(r);
        }
    }

    public static int[] max(int[] num){
        return max(num,num.length-1);
    }

    public static int[] max(int[] num,int length){
        int[] re = Arrays.copyOfRange(num,0,length);
        for(int i=1;i<=num.length-length;i++){
            if(sum(re) < sum(Arrays.copyOfRange(num,i,i+length) ) ){
                re = Arrays.copyOfRange(num,i,i+length);
            }
        }
        if( length>2 && sum(max(num,length-1))>sum(re)  ){
            re = max(num,length-1);
        }
        return re;
    }

    public static long sum(int[] num){
        long re = 0;
        for(int n:num)  re += n;
        return re;
    }

#18

public static void main(String[] args) {
        int[] arr = {-1,3,5,-3,4,4,2,7,-9};
        int[] result = countMaxSum(arr);
        System.out.println(result.length);
        for(int i=0;i<result.length;i++) {
            System.out.print(result[i]+" ");
        }
    }
    
    public static int[] countMaxSum(int[] arr) {
        int sum = 0;
        int temp = 0;
        List<Integer> list = new ArrayList<>();
        List<Integer> listTemp = new ArrayList<>();
        for(int i=0;i<arr.length;i++) {
            if(arr[i]>=0) {
                sum += arr[i];
                list.add(arr[i]);
            }
            else {
                if(sum>temp) {
                    temp = sum;
                    listTemp = list;
                }
                sum = 0;
                list = new ArrayList<>();
            }
        }
        
        int[] rtnArr = new int[listTemp.size()];
        for(int j=0;j<listTemp.size();j++) {
            rtnArr[j] = listTemp.get(j);
        }
        return rtnArr;
    }

#19

public static void main(String[] args) {
int[] num = { -1, 2, 7, -9, 3, 6, 8, 2, -10 };
Integer[] result = getMaxArr(num);
int sun = 0;
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append("数组：");
for (int i = 0; i < result.length; i++) {
sun += result[i];
stringBuffer.append(result[i] + " ");
}
stringBuffer.append("\n最大和：" + sun);
System.out.println(stringBuffer.toString());
}

private static Integer[] getMaxArr(int[] arr) {
int sun = 0;
int maxsun = 0;
int len = arr.length;
List maxList = new ArrayList();
List list = null;
for (int i = 0; i < len; i++) {
sun = 0;
list = new ArrayList();
for (int j = i; j < len; j++) {
sun += arr[j];
list.add(arr[j]);
if (sun >= maxsun) {
maxsun = sun;
maxList.clear();
maxList.addAll(list);
}
}
}
Integer[] result = new Integer[maxList.size()];
result = (Integer[]) maxList.toArray(result);
return result;
}

#20

        int[] list={-1,2,7,-9,3,6,8,2,-10};
        List<Integer> sumList=new LinkedList<Integer>();
        List<Integer> maxList=new LinkedList<Integer>();
        int max=0;
        int sum=0;
        for(int i=0;i<list.length;i++){
            sum=0;
            sumList.clear();
            for(int j=i;j<list.length;j++){
                sum+=list[j];
                sumList.add(list[j]);
                if(sum>=max){
                    max=sum;
                    maxList.clear();
                    maxList.addAll(sumList);
                }
            }
        }
        System.out.println(max);
        System.out.println(maxList);

#21

来学习大神好算法的

#22

我记得这是一套竞赛题目，好像好的算法是O(N)还是O(nlogn）的，反正暴力无脑的算法，不会有的。数据规模得上万吧

#23

import java.util.HashMap;
import java.util.Map;
/**
 * 原题：
         给定一个数组 int[] num = {-1,2,7,-9,3,6,8,2,-10};【数组不是固定的，是任意数组这只是个例子】
     要求：
         将数组中任意连续的项求和的最大值，并输出新的数组。
         举例：3+6+8+2 = 19，在没有任何连续的想加大于19，所以输出 [3,6,8,2]，最大和：19 。
 * 
 * 思路：通过Map的key和value，key可以用来保存和sum，value用来保存对应的数组
 * 但是，数组存在最大值可能对应多个数组，题目中最大值19对应的[3,6,8,2]、[2,7,-9,3,6,8,2]两个数组，key值会被覆盖
 * 于是改变一下思路：创建一个array数组，把sum值保存在一个数组中，下标从0开始，
 * 然后把sum对应的数组保存在value中，key的值和array数组的下标相同，这样就能通过下标把sum和MAP中的value关联起来
 * 例如：array[0]=19  ---Map(key,value)对应(0,[3,6,8,2])
 * 这样就吧19 和 [3,6,8,2]关联起来了，19可以重复，就能对应多个数组了
 * @author yx
 * 2017-7-12
 */
public class Test {
	//map->key保存下标，从0开始，value保存对应的数组
	static Map<Integer, int[]> map = new HashMap<Integer, int[]>();

	//统计和，下标与map的key意义对应，因为key保存和的话，两个相同的会覆盖掉
	static int[] mapArray; 

	public static void main(String[] args) {
		int[] num = {-1,2,7,-9,3,6,8,2,-10};
		mapArray = new int[num.length*(num.length+1)/2]; 

		//数组长度为1的时候
		new Test().getMap(num, 1);

        //找到mapArray最大值
		int temp=0;
		for(int i=0; i<mapArray.length; i++){			
			if(mapArray[i] > temp){
				temp = mapArray[i];
			}
		}

		//循环找出最大值对应的数组
		System.out.println("最大值：" + temp);
		System.out.println("对应的数组：");
		for(int i=0; i<mapArray.length; i++){			
			if(mapArray[i] == temp){
				System.out.print("[" + map.get(i)[0]);
				for (int j = 1; j < map.get(i).length; j++) {
					System.out.print(","+map.get(i)[j]);
				}
				System.out.println("]");
			}
		}
	}

	int count = 0; //mapArray下标

	// n表示数组长度，递归实现所有可能的连续数组
	public void getMap(int[] aa, int n) {
		while (n <= aa.length) {
			if (n == 1) {
				for (int i = 0; i < aa.length; i++) {
					map.put(count, new int[] { aa[i] });
					mapArray[count++] = aa[i];
				}
				getMap(aa, n+1);
			} else {
				for (int i = 0; i <= aa.length - n; i++) {
					int sum1 = 0;
					int temp[] = new int[n];
					int begin = 0;
					for (int j = i; j < i + n; j++) {
						sum1 += aa[j];
						temp[begin++] = aa[j];
					}
					map.put(count, temp);
					mapArray[count++] = sum1;
				}
				getMap(aa, n+1);
			}	
			break;
		}
	}

}

输出结果：
最大值：19
对应的数组：
[3,6,8,2]
[2,7,-9,3,6,8,2]
这个结果是你想要的吗

#24

剑指offer第31题

#25

各位大神，我觉得解题思路不太难，是不是可以这么考虑：
首先审题：将数组中任意连续的项求和的最大值，并输出新的数组。就是说要将连续值相加求最大值！
分析：什么情况下，连续值相加会越加越小？只能因为出现负数！
ok，那么思路就很简单啦，先求出数组的长度，然后遍历每个值，记录负数值的坐标。将两两相近的负数值之间的正数相加，然后比较哪一组相加的值最大。这样就能找到如题的最大值了，并且对应负数值的坐标记录下来，也就能找到相对应的新数组的位置，最终形成新数组。

会Java的HR一枚，如分析不对还请指教。

#26

#27

从前向后遍历，
算法：a1+a2大于a2 取a1+a2，小于取a2
后续取上一步的结果作为新的a1重复上面运算，但要记录下来a1的组成，一直到数组遍历结束
遍历的过程中记录下a1的最大值，及最大值的组成
最后记录的a1最大值即为最大值，对应数组就是想要的数组

#28

 

	static void max(int[] num) {
		int max = 0;
		int max_left = 0, max_right = 0;
		int left = 0;
		int right = 1;
		int now = num[left];
		int now_max = now;
		/*
		 * 当一段连续熟加起来小于0 时 就准备放弃这一段 ，因为这一段和其他的相加肯定小于另一端
		 * 当这段出现过的最大值 与 最大值比较 
		 */
		for (; right < num.length;) {
			if (now <= 0) {
				if (now_max > max) {
					max_left = left;
					max_right = right;
					max = now_max;
				}
				left = right++;
				now = num[left];

			} else {
				now += num[right++];
				now_max = now > now_max ? now : now_max;
			}
		}
		if (now_max > max) {
			max_left = left;
			max_right = right - 1;
			max = now_max;
		}
		//此处已获得最大的段了 从右删除小于0的段
		left = max_left;
		right = max_right;
		now = num[right];

		for (;;) {
			if (now <= 0) {
				max_right = --right;
				now = num[right];
			} else {
				now += num[--right];
			}
			if (left == right - 1) {
				break;
			}
		}
		System.out.println(max_left);
		System.out.println(max_right);
		System.out.println(max);
		for (int i = max_left; i <= max_right; i++) {
			System.out.print(num[i] + " ");
		}

#29

等会上代码...

#30

static class Section{
		//连续大于等于0或小于0的数段和
		private int val;
		//start index 数段在原始数组内的起始索引
		private int si;
		//end index 数段在原始数组内的终点索引
		private int ei;

		//默认ei = si
		private Section(int val, int si) {
			this.val = val;
			this.si = this.ei = si;
		}

		//向当前数段添加下一数段,参数section必须紧接在当前数段
		private Section add(Section section) {
			val += section.val;
			ei = section.ei;
			return this;
		}

		//在数段中添加新数
		private Section add(int val) {
			this.val += val;
			ei++;
			return this;
		}

		//克隆当前数段
		public Section clone() {
			Section section = new Section(val, si);
			section.ei = ei;
			return section;
		}

		//使数组标准化为 正负间隔形式,并去除首末负数
		private static Section[] standardized(int[] arr) {
			ArrayList<Section> list = new ArrayList<>();
			if (arr.length == 0)
				return new Section[0];
			Section curr = new Section(arr[0], 0);
			for (int i = 1, l = arr.length; i < l; i++) {
				if ((curr.val >= 0) ^ (arr[i] < 0)) {
					curr.add(arr[i]);
				} else {
					list.add(curr);
					curr = new Section(arr[i], i);
				}
			}
			list.add(curr);
			if (list.get(0).val < 0)
				list.remove(0);
			if (list.get(list.size() - 1).val < 0)
				list.remove(list.size() - 1);
			return list.toArray(new Section[list.size()]);
		}

		//在数组中获取最大数段
		public static Section getMax(int[] arr) {
			Section[] sections = standardized(arr);
			//Arrays.stream(sections).forEach(System.out::println);
			Section max = sections[0];
			for (int i = 0, l = sections.length; i < l; i += 2) {
				Section tmp = null;
				for (int j = i; j < l; j += 2) {
					if (tmp != null)
						tmp.add(sections[j - 1]).add(sections[j]);
					else
						tmp = sections[i].clone();
					if (max.val < tmp.val)
						max = tmp.clone();
				}
			}
			return max;
		}

		public String toString() {
			return "[ max: " + val + " , start: " + si + ", end: " + ei + " ]";
		}
	}

	/**
	 * 生成随机数组
	 */
	public static int[] gnrtRandomArr() {
		int len = 5 + (int) (Math.random() * 10);
		int[] arr = new int[len];
		for (int i = 0; i < len; i++)
			arr[i] = 20 - (int) (Math.random() * 40);
		return arr;
	}

	public static void main(String[] args) {
		int[] arr = gnrtRandomArr();
		System.out.println(Arrays.toString(arr));
		Section max = Section.getMax(arr);
		System.out.println("max: " + max);
		System.out.print("num: ");
		for (int i = max.si, end = max.ei; i <= end; i++)
			System.out.print(arr[i] + " ");
	}

#31

我的思路不知道可不可行：
从第一个开始，遇到负数则跳过。开始累加。
一个存储最大值的变量，和当前累加序列的数组。
每次累加都比较下当前最大值，如果有更大的就更新数据，如果不大的就继续累加，如果累加的结果<=0，终止前面累加，从最后一个被加的数后开始继续累加。
最后就是最大的，代码现在没空写— 。—|| 

#32

把下标给整出来了
1 4 5 6 7