找到整數的最大連續總和在陣列

我有這個執行，這個程序的結果是100，但正確答案是103 是任何人都知道什麼是錯在這個實現或是否有更好的辦法用於查找數組中整數的最大連續和？找到整數的最大連續總和在陣列

在此先感謝。

#include <stdio.h> 

int main(void) { 
int a[] = { -3, 100, -4, -2, 9, -63, -200, 55 }; 
int max_sum, temp_sum, i, n = 12, t; 
temp_sum = max_sum = a[0]; 
for (i = 1; i < n; i++) { 
    if (a[i] > 0) 
     temp_sum += a[i]; 
    else { 
     t = 0; 
     while (a[i] < 0 && i < n) { 
      t += a[i]; 
      i++; 
     } 
     if (temp_sum + t > 0) { 
      temp_sum = temp_sum + t + a[i]; 
      if (temp_sum > max_sum) 
       max_sum = temp_sum; 
     } else if (i < n) 
      temp_sum = a[i]; 
    } 
} 
if (temp_sum > max_sum) 
    max_sum = temp_sum; 
printf("Maximum Numbers is %d \n", max_sum); 
return 0; 
}

來源

2012-04-10 Elnaz

這裏有smt怪異的，我把你的代碼複製到CodeBlocks，結果是332？ – 2012-04-10 19:48:45

這是功課嗎？你應該考慮使用遞歸。 – 2012-04-10 19:49:59

「最大連續數」是什麼意思？你怎麼能得到103？ – Saphrosit 2012-04-10 19:50:20

您沒有使用正確的索引：

在這裏看到演示：http://codepad.org/wbXZY5zP

int max_sum, temp_sum, i, n = 8, t; 
temp_sum = max_sum = a[0]; 
for (i = 0; i < n; i++) { 
    (...) 
}

來源

2012-04-10 19:54:58

so'n = 8'並且循環從0到7（所以'i = 0'作爲開始） – 2012-04-10 19:58:47

我建議Kadane's algorithm。在C++會是這樣的（未經測試）：

int maxSubarray(std::vector<int> a) { 
    int maxAll = 0, maxHere = 0; 
    for (size_t i = 0; i < a.size(); ++i) { 
     maxHere = std::max(a[i], maxHere + a[i]); 
     maxAll = std::max(maxAll, maxHere); 
    } 
    return maxAll; 
}

來源

2012-04-10 19:54:39 Skiminok

如果找最大連續總和不是從索引0開始，最簡單的方法是有兩個循環

int max_sum, temp_sum, i, n = 8, t; 
max_sum = a[0]; 
for (t = 0; t < n; t++) { 
    temp_sum = 0; 
    for (i = t; i<n; i++) { 
     temp_sum += a[i]; 
     if (temp_sum > max_sum) 
      max_sum = temp_sum; 
    } 
}

來源

2012-04-10 20:06:11

正如其他用戶所指出的，您的實施指數不正確。但是，我認爲有必要添加一個答案，指出如果所有值均爲負值（最接近正值的數字不在第一位），則您的實現失敗。

要快速解決這一問題將在情況下a[i] < 0 && temp_sum + t < 0分配溫度和當增加一個檢查 - 在最後else塊。

} else if (i < n) { 
    temp_sum = a[i]; 
    if (temp_sum > max_sum) 
     max_sum = temp_sum; 
}

來源

2012-04-10 20:12:35

找到整數的最大連續總和在陣列

回答

相關問題