如何获得所有项目的最大总和的子数组

-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

如何获得所有项目的最大总和的子数组

回答

相关问题