如何在java中查找最大序列和的子数组？

如果数组是{-1 3 -1 9 4 -4}。我想输出为如何在java中查找最大序列和的子数组？

“总和为15，数组为{3 -1 9 4}。”

我有总和的代码，但如何得到这个子数组？

这里是总和

int maxSum = 0, thisSum = 0; 
    for(int j = 0; j < a.length; j++){ 
     thisSum += a[ j ]; 
     if(thisSum > maxSum){ 
      maxSum = thisSum; 
     } 
     else if(thisSum < 0) 
      thisSum = 0; 
    } 
    System.out.println(maxSum);

来源

2016-09-19 Mayur Tolani

Look [here]（http://www.programcreek.com/2013/02/leetcode-maximum-subarray-java/）。 – DimaSan

当你更新'maxSum'（也可能是'maxEnd'）时，保持'maxStart'（基于'j'）。 –

@DimaSan，只是返回最大总和 –

只记得从和到0和总和为零时，它可能意味着你有一个空的子阵列（说全部都是负数）。

int []a = {-1, 3, -1, 9, 4, -4}; 

    int from=0, to=0; 

    int maxSum = 0, thisSum = 0, thisFrom = 0 ; 
    for(int j = 0; j < a.length; j++){ 

     if (thisSum == 0){ thisFrom = j ; } 

     thisSum += a[ j ]; 
     if(thisSum > maxSum){ 
      from = thisFrom; 
      to = j; 
      maxSum = thisSum; 
     } 
     else if(thisSum < 0) 
      thisSum = 0; 
    } 
    System.out.println(Arrays.toString(Arrays.copyOfRange(a, from, to+1))); 
    System.out.println(maxSum);

来源

2016-09-19 22:35:50

就像一个魅力。谢谢。 –

代码如果您有总和，这意味着在你的代码的某个时刻，你的代码知道它到这一点最大的价值。为什么不把序列保存在每个总和的字符串中，并且每当总和最大时将字符串替换为下一个序列，最后您将获得总和值已经存在于maxSum变量中的序列。

来源

2016-09-19 22:19:08

如何在java中查找最大序列和的子数组？

回答

相关问题