如何在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中查找最大序列和的子數組？

回答

相關問題