如何獲得所有項目的最大總和的子數組

-2

我的測試是解決以下問題：給出了一個由零個整數組成的零索引數組A. 編寫一個解決方案來找出A的子數組，其中包含具有其所有項目的最大總和的後續項目。如何獲得所有項目的最大總和的子數組

實施例：

A = [2, -1, 3, -3, 4, -9, 10, -3, 4, -4, -7, 2, 8]。答案是[10, -3, 4]
A = [3, 2, -5, 7, 4, -8, 3, -5, 2, 4, -2, 4]。答案是[7, 4]
A = [-2, 5, 3, 6, -1,-5]。答案是[-2, 5, 3, 6]。

請幫我給我解決它的方法。

來源

2016-08-12 user1186850

你做了什麼來解決它？ –

發佈作業？如果我們剛剛發佈了答案，您如何期望學會如何解決問題？這可以通過幾十種方式解決。你有什麼嘗試？什麼地方出了錯？你停在哪裏？ – user3185569

我還沒有找到解決它的解決方案。請指導我解決問題的理想。 – user1186850

基本上，你需要做的是遍歷數組並檢查元素總和的最大值。一旦你找到了最大和，你有你的結果子陣列的最後一個元素。找到最大元素後，您需要遍歷並執行相同操作，以便找到具有最大元素總和的子數組。

int iNewTopHigh = 0; 
int iNewTopLow = 0; 
int iIndNewTopHigh = 0; 
int iIndNewTopLow = 0; 
int iSumHigh = 0; 
int iSumLow = 0; 

int[] iArr = {2, -1, 3, -3, 4, -9, 10, -3, 4, -4, -7, 2, 8}; 
       //{3, 2, -5, 7, 4, -8, 3, -5, 2, 4, -2, 4}; 
       //{-2, 5, 3, 6, -1,-5}; 
//Get the top 
for(int i = 0; i < iArr.Length; i++){ 
    iSumHigh += iArr[i]; 
    if(iSumHigh > iNewTopHigh){ 
     iIndNewTopHigh = i; 
     iNewTopHigh = iSumHigh;    
    }   
} 
//Get the bottom 
for(int i = iIndNewTopHigh; i != 0; i--){ 
    iSumLow += iArr[i]; 
    if(iSumLow > iNewTopLow){ 
     iIndNewTopLow = i; 
     iNewTopLow = iSumLow; 
    } 
} 
//Print results 
for(int i = iIndNewTopLow ; i <= iIndNewTopHigh; i++){ 
    Console.Write(iArr[i] + ", "); 
}

來源

2016-08-12 08:14:46 Gnqz

謝謝。它運行得更快，我的嵌套循環。 – user1186850

如何獲得所有項目的最大總和的子數組

回答

相關問題