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

15个回答

︿ 2
用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;
    }
︿ 2
不考虑性能,如果9个数  分9次   第一次 算  一个区间的最大值 1 2 3 4 5 6 7 8 9
第二次  12 23 34 45 56




这样不就ok
︿ 1
简单写了一个,没考虑性能,结果也只取了一组.
 

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;
    }

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

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,直到数组不再发生变化
︿ 0
个人感觉:两层循环,外层循环是数组,内层循环是从外层选中数组的下标开始往后挨个加,每加上一个数就跟前一个数比较,如果大就保留,如果小就舍弃,内层循环结束后,把这个循环得出的最大数放到list里面,然后等外层循环结束后把list排个序就OK了,这样可能好点吧。
︿ 0
想起了  “ 数据结构与算法分析 java ”   里面有这个问题的详解 ,可是我都忘了  
︿ 0
        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);
︿ 0
如果数组是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;
    }
}
︿ 0
我的思路是先算出每项叠加的和,如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后多个最终数组的长度刚好相同的情况,我懒就不加了
//另外个人水平有限,有不对的地方欢迎各位指出

︿ 0
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;
}
︿ 0

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;
    }

但是这个只能计算最大连续的和,却无法统计出连续的数组,希望大神给算法
︿ 0
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;
    }