一道面试题，看看怎么求解最好

Question

给定一个数组，当中有正负数，求当中的一段“子数组”（即任意长度，连续的数字），使得这个“子数组”的和是所有“子数组”和中最大的，
如给定的数组为12， -8， 5， 66， -21， 0 ，35， -44，7，则最大的和的子数组为{12， -8， 5， 66， -21， 0 ，35}，最大的和为89.

Answer 1

回1楼，“子数组”是指原数组中连续的一段数字，长度可以从1到数组的length

Answer 2

似乎只能用循环了一个个做和然后保留最大值的下标，二维数组应该可以array[x][y],x表示在原数组中的起始位置，y表示新数组长度或者是结束位置一个个死做

Answer 3

class Test
{ 
public static void main(String[] args)
{
   int s[]={12,-8,5,66,-21,0,35,-44,7};
   int k=s[0];
   int add[]=new int[10];
   int b=0;
   int i;
   int j;
   for(i=0;i<add.length;i++)
   {
   for(j=0;j<i;j++)add[i]+=s[j];
   if(add[i]>k)
   {
   k=add[i];
   b=i;
   }
   }
   System.out.print("{");
   for(i=0;i<b;i++)
   System.out.print(s[i]+",");
   System.out.println("}");
   System.out.print(k);
    } 
} 

Answer 4

没找到其他的简洁方法，看样子得穷举了。不知道你有没有学HashTable，你可以用循环一个个穷举，同时将新数组作为键，新数组以及和作为值存入HashTable，最后比较和的大小，从而得到最大和相对应的新数组。

Answer 5

import java.util.Arrays;public class MaxSum {    /**
     * 给定一个数组，当中有正负数，求当中的一段“子数组”（即任意长度，连续的数字），使得这个“子数组”的和是所有“子数组”和中最大的，
     * 如给定的数组为12， -8， 5， 66， -21， 0 ，35， -44，7，则最大的和的子数组为{12， -8， 5， 66， -21， 0
     * ，35}，最大的和为89.
     * 
     * @param args
     */
    public static void main(String[] args) {
        int[] a = { 12, -8, 5, 66, -21, 0, 35, -44, 7 };
        int[] b = max(a);
        System.out.println(Arrays.toString(b));
    }    private static int[] max(int[] a) {
        int header = 0;
        int tailor = a.length - 1;
        
        // remove header 
        while (header < tailor) {
            if (a[header] < 0) {
                header++;
            } else if (a[header] + a[header + 1] < 0) {
                header += 2;
            } else {
                break;
            }
        }        // remove tailor
        while (header < tailor) {
            if (a[tailor] < 0) {
                tailor++;
            } else if (a[tailor] + a[tailor - 1] < 0) {
                tailor -= 2;
            } else {
                break;
            }
        }
        
        return Arrays.copyOfRange(a, header, tailor + 1);
    }}

Answer 6

import java.util.Arrays;public class MaxSum {    /**
     * 给定一个数组，当中有正负数，求当中的一段“子数组”（即任意长度，连续的数字），使得这个“子数组”的和是所有“子数组”和中最大的，
     * 如给定的数组为12， -8， 5， 66， -21， 0 ，35， -44，7，则最大的和的子数组为{12， -8， 5， 66， -21， 0
     * ，35}，最大的和为89.
     * 
     * @param args
     */
    public static void main(String[] args) {
        int[] a = { 12, -8, 5, 66, -21, 0, 35, -44, 7 };
        int[] b = max(a);
        System.out.println(Arrays.toString(b));
    }    private static int[] max(int[] a) {
        int header = 0;
        int tailor = a.length - 1;
        
        // remove header 
        while (header < tailor) {
            if (a[header] < 0) {
                header++;
            } else if (a[header] + a[header + 1] < 0) {
                header += 2;
            } else {
                break;
            }
        }        // remove tailor
        while (header < tailor) {
            if (a[tailor] < 0) {
                tailor++;
            } else if (a[tailor] + a[tailor - 1] < 0) {
                tailor -= 2;
            } else {
                break;
            }
        }
        
        return Arrays.copyOfRange(a, header, tailor + 1);
    }}

Answer 7

import java.util.Arrays;public class MaxSum {    /**
     * 给定一个数组，当中有正负数，求当中的一段“子数组”（即任意长度，连续的数字），使得这个“子数组”的和是所有“子数组”和中最大的，
     * 如给定的数组为12， -8， 5， 66， -21， 0 ，35， -44，7，则最大的和的子数组为{12， -8， 5， 66， -21， 0
     * ，35}，最大的和为89.
     * 
     * @param args
     */
    public static void main(String[] args) {
        int[] a = { 12, -8, 5, 66, -21, 0, 35, -44, 7 };
        int[] b = maxSum(a);
        System.out.println(Arrays.toString(b)); // [12, -8, 5, 66, -21, 0, 35]
        
        a = new int[] {3};
        b = maxSum(a);
        System.out.println(Arrays.toString(b)); // [3]        a = new int[] {3, -4, 2};
        b = maxSum(a);
        System.out.println(Arrays.toString(b)); // [3]
        
    }    private static int[] maxSum(int[] a) {        if (a.length <= 1) {
            return a;
        }        int header = 0;
        int tailor = a.length - 1;        // remove header
        while (header < tailor) {
            if (a[header] < 0) {
                header++;
            } else if (a[header] + a[header + 1] < 0) {
                header += 2;
            } else {
                break;
            }
        }        // remove tailor
        while (header < tailor) {
            if (a[tailor] < 0) {
                tailor++;
            } else if (a[tailor] + a[tailor - 1] < 0) {
                tailor -= 2;
            } else {
                break;
            }
        }        // all removed
        if (header == tailor) {
            return new int[] { max(a) };
        }
        return Arrays.copyOfRange(a, header, tailor + 1);
    }    private static int max(int[] a) {
        int result = a[0];
        for (int i : a) {
            if (i > result) {
                result = i;
            }
        }
        return result;
    }}

Answer 8

代码就不贴了！说说思路：
通过计算来选择，肯定是最苯的。因为太耗时间了，所以我就想通过查找来做；
从最后一个开始查找，若为正数，标记为1，若为负数标记为0，(标记数组设置为sign[])指针往前跳一个；
设置一个if（a[i]=1&&a[i-1]=0）{if(a[i]+a[i-1]>=0)sign[i]=0;m=i;i--;}i=m;
//判断是否应该将此负数插入最大子串中；
if(i=0)//到达给定串的头指针；
for(;sign[i]==0;)
{printf();}

Answer 9

不好意思！弄错了一点点！！先修正如下：
代码就不贴了！说说思路：
通过计算来选择，肯定是最苯的。因为太耗时间了，所以我就想通过查找来做；
从最后一个开始查找，若为正数，标记为1，若为负数标记为0，(标记数组设置为sign[])指针往前跳一个；
设置一个if（a[i]=1&&a[i-1]=0）{if(a[i]+a[i-1]>=0)sign[i]=1;m=i;i--;sign[i]=0;}i=m;
//判断是否应该将此负数插入最大子串中；
if(i=0)//到达给定串的头指针；
for(;sign[i]==1;)
{printf();}

Answer 10

public class Test11 {
public static void main(String[] args)
{
   int s[]={-100,-100,-100,-100,100};
   int add[]=new int[10];
   int k=s[0];
   add[0]=s[0];    
           int b=0;//标记位
   int i;
   int j;
   for(i=0;i<s.length;i++)
   {
  for(j=0;j<i;j++)add[i]+=s[j];
  if(add[i]>k)//这里i自动加1了，所以出现0位置没有附值~
   {
   k=add[i];
   b=i;//记录位置
   }
   }
   for(i=0;i<=b;i++)
   System.out.print(s[i]+" ");
           System.out.println();
   System.out.print(k);
    } 
}

Answer 11

答：参考代码如下：
public class GetLongSeq {
  private static int[] a={12,-8,5,66,-21,0,35,-44,7};
//private static int[] a={-100,-100,-100,-100,100};
  private static int ci,cj,cv;
  private static void find()
  {
int head=0,tail=a.length-1;
while(head<tail && a[head]<0){head++;}//去掉头
while(head<tail && a[tail]<0){tail--;}//去掉尾
int i=head,j=tail,temp=0;//当前已找到的子串的开始处，结束处与当前的最大值
ci=i;cj=i;cv=a[i];
for(;i<=tail;i++)//从i开始进行连续子串找
{
if(a[i]<0){continue;}//若开头的值小于０，显然不用考虑
temp=a[i];
for(j=i+1;j<=tail;j++)
{
temp=temp+a[j];//当前子串的和
if(temp>cv){//找到更大的，记下子串
ci=i;cj=j;cv=temp;
}
}//for(j)

}//for(i)
  }
 private static void print()
  {
 System.out.print("{");
for(int i=ci;i<=cj-1;i++) 
{
System.out.print(a[i]+",");
}
System.out.print(a[cj]+"} 和＝"+cv);
  }
public static void main(String[] args) {
find();
        print();
}}
运行结果：{12,-8,5,66,-21,0,35} 和＝89
若是：{-100,-100,-100,-100,100}，则结果：{100}和＝100
程序思路：思路见程序注释。时间复杂性：O(n2),因为是双重循环。

Answer 12

答：ci=i;cj=i;cv=a[i];//当前已找到的子串的开始处，结束处与当前的最大值

Answer 13

思路:  1:找出数组中最大的数;  2:在原始数组的第一个数到最大的数的前一个数之间,从第一个非负数开始累加其后的数组元素,其结果一旦为负,放弃.再从下一个元素起到最大的数的前一个数之间,从第一个非负数开始累加其后的数组元素,其结果一旦为负,放弃;否则记下起始元素的下标a.
  3: 在原始数组的最后一个数到最大的数的下一个数之间,从最后一个非负数开始累加其前的数组元素;其结果一旦为负,放弃;再从前一个元素起到最大的数的下一个数之间,从第一个非负数开始累加其前的数组元素;其结果一旦为负,放弃;否则记下起始元素的下标b.  4:原始数组从a到b的元素就是所求子数组;

Answer 14

你可以这样试试.
我运行过可以的.
---------------------------------------------------------------------------------------------------
import java.util.Scanner;public class ArraysSumAndMax { /**
 * @param args
 */
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入一个数组序列以\",\"号分隔");
String[] strArrays = sc.nextLine().split(",");
Double[] arraysNum = new Double[strArrays.length];
double max = Double.MIN_VALUE, sum = 0;
try {
for (int i = 0; i < strArrays.length; i++) {
arraysNum[i] = Double.parseDouble(strArrays[i]);
if (arraysNum[i] > max) {
max = arraysNum[i];
}
sum += arraysNum[i];
}
} catch (NumberFormatException e) {
System.out.println("输入格式有错或有不可法的符号");
}
System.out.println("最大的数为：" + max);
System.out.println("和为：" + sum);
}
}

Answer 15

不好意思.原来负的不加呀.
import java.util.Scanner;public class ArraysSumAndMax { /**
 * @param args
 */
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入一个数组序列以\",\"号分隔");
String[] strArrays = sc.nextLine().split(",");
Double[] arraysNum = new Double[strArrays.length];
double max = Double.MIN_VALUE, sum = 0;
try {
for (int i = 0; i < strArrays.length; i++) {
arraysNum[i] = Double.parseDouble(strArrays[i]);
if (arraysNum[i] > max) {
max = arraysNum[i];
}
if(arraysNum[i]>0){
sum += arraysNum[i];
}
}
} catch (NumberFormatException e) {
System.out.println("输入格式有错或有不可法的符号");
}
System.out.println("最大的数为：" + max);
System.out.println("和为：" + sum);
}
}

Answer 16

最终程序出来了，不改了，哈哈public class Test11 {
public static void main(String[] args)
{
   int s[]={-100,100,100,-100,100};
   int add[]=new int[100];
   int k=s[0];
   int b=0;//标记开始位置
   int p=0;//标记结束位置
   int i;
   int j;
   
   for(i=0;i<=s.length;i++)//整体循环
   {
  for(j=i;j<s.length;j++)//子数组循环
  {
  add[i]+=s[j];
      if(add[i]>k)
   {
   k=add[i];
   b=i;//获得开始位置下标
   p=j;//获得结束位置下标
   }
   }
   }
   System.out.print("{");
   for(i=b;i<=p;i++)
   System.out.print(s[i]+" ");
   System.out.println("}");
   System.out.print(k);
    } 
}

Answer 17

{....a，b，c，d，....e}
a是数组中第一个非负数，如果b >= 0，则最大数组中加上b,如果b是负的，则计算b到e的所有数的和，如果大于0则最大数组中应该包括b，然后依次计算c。否则当前数组就是要求的数组了。

Answer 18

分组索引
索引段{每个索引段表示了数组中的一段连续的元素，包含属性[总值=SUM(元素的值)] }
再数组是一个全集的情况下 
将数组分为连续的子索引段
第一次情况下 每个元素是一个独立索引段 
然后 遍沥每个索引段 从遍沥开始 相加遍沥的 索引段的值
关键逻辑{
      if((当前索引段的总值+相邻索引段的总值)>=当前索引段总值){
           合并2个索引段为当前索引段
      }else{相邻索引段 作为 当前 索引段 开始继续}      END:本次遍沥没有进行索引段组合的话 则返回 最大的一个索引段
}

Answer 19

 思路很简单定义2个变量:a 记录所求数组ARR1的和; b  记录原来数组中ARR1后面的所有元素之和从第一个正数开始一个元素一个元素往后面加,存入a,
每加入一个元素同时后面计算剩下的所有元素的和,存入b,
如果和>0,则继续加,如果<0,则停止.此时所得到的a为所求数组.

Answer 20

----------------------------------------------------------------------------------------------------
基本同意7楼！
1.先找出数组中的最大值max
2.每i个相邻的元素相加。如果某一组i个数的第一个或者最后一个是负数或者0，则跳转到下一组i个数；如果这i个数的和大于 
  max,将这组数保存到数组max[]中，同时更改max的值（i从2到数组的长度）
3.输出max[]和max

Answer 21

int MaxSubsequenceSum4(const int A[], int N){int ThisSum, MaxSum, i;ThisSum = MaxSum = 0;for(i = 0; i < N; i++){ThisSum += A[i];if(ThisSum > MaxSum)MaxSum = ThisSum;else if(ThisSum < 0)ThisSum = 0;}return MaxSum;}或在百度中搜最大子序列和算法即可

Answer 22

呵呵，似乎之前做过。
maxsum ← 0
  for i ← 0 to n-1
      sum ← 0
      for j ← i to n-1
          do sum ← sum + A[j]
            if sum > maxsum
                maxsum ← sum
print maxsum

Answer 23

这就是个简单的典型的“动态规划”题目。数组：x1,x2,x3,……xn
思路，首先是寻找最优子结构，这点要依靠一些经验规则。
这里的最优子结构就是
f(i)定义为以xi结尾的最大字串和。
那么f(i+1)就可以考虑
如果xi+1大于等于0或者f(i) + xi+1 > 0，那么f(i+1) = f(i) + xi+1；
如果f(i) + xi+1 <= 0,那么f(i+1) = 0；
递推公式就是有了。下面用DP的典型结构给出代码：
public class MaxSubSequence {    
    public static void main (String[] args) {
     int[] input = new int[]{3,73,-95,42,43,29,-30,-87,74,-53,22,74,-91,-1,-27,-8,-14,26,-67,-74};
    
     int[] fDp = new int[input.length]; //f for dp
//process first element
if (input[0] > 0)
fDp[0] = input[0];
     for (int i = 1;i < input.length;++i){
     if (fDp[i-1]+input[i] > 0)
     fDp[i] = fDp[i-1]+input[i];
     else
     fDp[i] = 0;
     }
     //find the max value in fDp
     int maxSun = 0;
     for (int sum : fDp)
     if (sum > maxSun)
     maxSun = sum;
    
     System.out.println("max sum : " + maxSun);
}
    
}
程序输出117
这里得到了正确结果，但是要求字串的位置还没实现，其实很简单，修改程序，从结果反推过程就可得到。上面是个典型的一维DP结构的解法，算法复杂度是O（n），但是想更直接的求解，可以优化算法，不用显示创建DP数组。class MaxSubSequence2{
public static void main (String[] args) {
     int[] input = new int[]{3,73,-95,42,43,29,-30,-87,74,-53,22,74,-91,-1,-27,-8,-14,26,-67,-74};

int fst = -1,snd = -1,tFst = 0,tSnd = 0,maxSum = 0,currSum = 0;
for (;tSnd < input.length;++tSnd){
currSum += input[tSnd];
if (currSum > maxSum){
maxSum = currSum;
fst = tFst;
snd = tSnd;
}
if (currSum < 0){
currSum = 0;
tFst = tSnd+1;
}
}

System.out.println("max sum : " + maxSum + " from " + fst + " to " + snd);
}
}
 
注：没有考虑全负数的数组，修改一点就能满足。

Answer 24

答：仅求子串的最大和（找不出子串），则只要O(n)级就行了。
　　若既要求出子串的最大和，同时求出子串本身，则：目前给出的都是O(n2)级。
　　谁要给出一个O(n*lgn)级的程序，能：既求出子串的最大和，同时又求出子串本身？

Answer 25

51楼已经很不错了，加上数组是全负的处理一下就可以了，也就是当maxsum为0的时候，找出数组中最大元素就可以了

Answer 26

只说一下我的思路：
1、对数据进行降幂排序；
2、判断子数组需要的长度n是否大于原数组a[]长度m的1/2;是，则跳到第3步，否则进入第4步；
3、对排序后的原数组提取元素a[0]－a[n]，生成需要的子数组；
4、对排序后的原数组提取元素a[(m-n)]..a[m],生成需要的子数组；
5、根据原数组顺序还原子数组顺序；
6、over考虑程序性能和边界，可在第2步之前加入对n的判断，n<0时，子数组为b[0]{};n=1时，子数组为b[max(a[])];n>m时，子数组为a[]
主要性能瓶颈可能出现在还原数组上，因为用数组方式，不好做元素的增删操作，所以可以考虑将数组首先变成LinkedArrayList，在添加的时候将数组的元素及其位置封装成对象添加到List中，得到了子List后，根据其中的位置再进行一次排序，然后还原成数组。

Answer 27

连续子系列是个很经典的问题，有三种方法，但时间复杂度不相同，其中有上面的朋友说的方法，这里就说一种最简单的方法，如下：假如 在一个已知序列中查找和最大的子序列：-7，15，2，-5，12，6，-26，找到最大子序列为15，2，-5，12，6，代码为：
public static int maximumSubsequenceSunm(int []a)
   {
        int maxSum=0,  thisSum=0;
        int seqStart=i,seqEnd=j;
        for(int i=0 , j=0;j<a.length;j++)
        {
           thisSum+=a[j];
           if(thisSum>maxSum)
           {
              maxSum=thisSum;
              seqStart=i;
              seqEnd=j;
           }
       else if(thisSum<0)
        {
            i=j+1;
            thisSum=0;
         }
       retrun maxSum;
    }

Answer 28

12， -8， 5， 66， -21， 0 ，35， -44，7
思路只能以正数开头的遍历，那么就有5个最大的连续片断，再在这5个中选择最大的即可关键在于遍历时候的筛选
循环过程先以12开头循环
12   
12, -8      -8<0 所以12,-8排除
12，-8，5     5>0 but (-8+5)<0  12,-8,5 排除
12，-8，5，66    66>0 and (-8+5+66)>0   不排除
12,-8,5,66,-21  -21<0 排出12,-8,5,66,-21 ，0  排出
12,-8,5,66,-21 ，0  ，35   35>0 and(-21+0+35)>0 不排除12,-8,5,66,-21 ，0  ，35 ，-44  -44<0  排除
12,-8,5,66,-21 ，0  ，35 ，-44，7    7>0 and (-44+7)<0 排除
所以到最后就是12,-8,5,66,-21 ，0  ，35  循环最后一个不排除的组合89再以-8 开头 -8<0 排除再以5开头
5
5，66  66〉0 不排除
依次类推也可以得出一个最大以下重复循环即可最后在所以的最大中找出一个最大来即可
key:关键在于排除的规则 以便缩小范围

Answer 29

，“子数组”是指原数组中连续的一段数字，长度可以从1到数组的length 

Answer 30

public static void maxChildArry(int[] superArry) {
int maxcount = 0;
int begin = 0;
int end = 0;
for (int i = 0; i < superArry.length - 1; i++) {
int temp = 0;
if (superArry[i] > 0) {
for (int j = i; j < superArry.length; j++) {
temp += superArry[j];
if (maxcount < temp) {
maxcount = temp;
begin = i;
end = j;
}
}
}
}
System.out.println("最大的子数组为:");
for(;begin<=end;begin++){
System.out.print(superArry[begin]+"   ");
}
System.out.println("\n他们和和为:"+maxcount);
}

Answer 31

public static void maxChildArry(int[] superArry) {
int maxcount = 0;
int begin = 0;
int end = 0;
for (int i = 0; i < superArry.length - 1; i++) {
int temp = 0;
if (superArry[i] > 0) {
for (int j = i; j < superArry.length; j++) {
temp += superArry[j];
if (maxcount < temp) {
maxcount = temp;
begin = i;
end = j;
}
}
}
}
System.out.println("最大的子数组为:");
for(;begin<=end;begin++){
System.out.print(superArry[begin]+"   ");
}
System.out.println("\n他们和和为:"+maxcount);
}

Answer 32

有点问题哦。
你这里仅仅处理了大于0的情况，也就是直接屏蔽掉了负数。所以也如你所说，如果全是负数就不行了。
f(i)定义为X[i]结尾的最大字符和，那么f(i+1):
f(i)<0:f(i+1) = X[i+1]
f(i)>0:f(i+1) = f(i)+X[i+1]若某个f(i)==0，且刚好它处于最大子串的首位，那子串的结果就有多个了（sum大小一定）帖代码验证一下吧：public class Test {
public static void main(String[] args) { int[] input = new int[] { 3,73,-95,42,43,29,-30,-87,74,-53,22,74,-91,-1,-27,-8,-14,26,-67,-74 }; int[] fDp = new int[input.length]; // f for dp
int[] starter = new int[input.length]; // remember start point

// won't process empty array.
if (input.length == 0) {
return;
}
// process first element
fDp[0] = input[0];
starter[0] = 0; for (int i = 1; i < input.length; ++i) {
if (fDp[i - 1] >= 0) { // 0 might be processed in later version.
fDp[i] = fDp[i - 1] + input[i];
starter[i] = starter[i - 1];
} else {
fDp[i] = input[i];
starter[i] = i;
}
}
// find the max value in fDp
int index = 0;
for(int i=1;i<input.length;i++){
if(fDp[i] > fDp[index]) {
index = i;
}
} System.out.println("max sum : " + fDp[index]);
System.out.println("array range : " + starter[index]+"~" + index);
}
}

Answer 33

#include "stdafx.h"#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int a[7] = {12,-8,5,66,-21,0 ,35}; int maxsum = 0;
int sum = 0;
for(int i =0;i<7;++i)
{
sum+=a[i];
if(sum  > maxsum)
{
maxsum = sum;
}
else if(sum < 0)
{
sum = 0;
}
} cout<<maxsum<<endl;

return 0;
}

Answer 34

public static void main(String[] args) {
//~~~~~~~~~~~~~赋初始值~~~~~~~~~
int a[] = {12,-8,5,66,-21,0,35,-44,7}; //原始数组
List al1 = new ArrayList();
for(int z = 0;z<a.length;z++){ //存到集合中便于操作
al1.add(new Integer(a[z]));
}
List b1 = new ArrayList(); //标记数族
int sum = 0; //存最大的集合值
//~~~~~~~~~~~~~找最大子数组
for(int i = 1;i <= a.length;i++){ //从1到9的截取子数组
for(int j = 1;j <= a.length + 1 - i;j++){

if(a[j-1] < 0){ //优化 如果开头小于0 显然不用考虑
continue;
}
if(a[j-1+i]<0){ //优化 结尾小于0 显然不用考虑
continue;
}
List temp = al1.subList(j-1,j-1+i); //截取集合
int sumTemp = 0; //存各个小集合的和

for(int z = 0;z<temp.size();z++){ //求和
sumTemp = sumTemp + (Integer)temp.get(z);
}


if(sum < sumTemp){
sum = sumTemp; //保留最大和及该集合
b1 = temp;
}

}//for(j)
}//for(i)
//~~~~~~~~~~~~打印~~~~~~~~~~~~~~~~~
System.out.println("最大和是"+sum);
for(int x = 0;x < b1.size();x++){
System.out.println(b1.get(x));
}
}

Answer 35

17#看下这组数据 int[] a = { 12, -8, -5, 6, -21, 0, 35, 44, 7 };

Answer 36

先求出数组中能加出的最大数MAX，比如数组{12， -8， 5， 66， -21， 0 ，35， -44，7}，MAX=12+5+66+35+7
再从数组第一个元素开始求子数组，每遇到负元数，就记下与MAX的差值，这样遍历完数组后，与MAX差值最小的子数组就是所求。
代码就算了，写起来应该不难，呵呵。

Answer 37

先求出数组中能加出的最大数MAX，比如数组{12， -8， 5， 66， -21， 0 ，35， -44，7}，MAX=12+5+66+35+7
再从数组第一个元素开始求子数组，每遇到负元数，就记下与MAX的差值，这样遍历完数组后，与MAX差值最小的子数组就是所求。
代码就算了，写起来应该不难，呵呵。

Answer 38

呃 双层循环有点低效 但是直观int array[]{12,-8,5,66,-21,0,35,-44,7};int start,end;
int maxSum=array[0];for(int startIndex=0;startIndex<array.length();++startIndex)
{
    for(int endIndex=StartIndex+1;endIndex<array.length();++endIndex)
    {
        int temp=array[startIndex]+array[endIndex];
            if(temp>maxSum)
            {
                maxSum=temp;
                start=startIndex;
                end=endIndex;
            }
    }
}
System.out.println......                                           end

Answer 39

33楼add为什么要用数组呢》？

Answer 40

之前理解错误了，没影响结果，也就没改，
里面就是存了下标为0->s.length，1->s.length的和。