2015-11-01 84 views
0

我正在學習C,我的老師給了我一個任務,但我被卡住了。 陣列中有10個正數,我需要找到3個連續數字,並且總數最高。我在網上找到了這個解決方案,但我如何找到3個連續的數字並將它們相加?我應該如何處理這個問題?我應該在陣列中尋找最大的數字並從那裏出發? 我發現的代碼做了迄今爲止我所做的更好的工作。C從數組中連續輸出3個數字的最大總和

陣列具有:{1,2,3,2,0,5,1,6,0,1},那麼3個數字的最大總和將是{1,2,3,2,0,5,1,6,0,1},因爲它給12

#define N_ELEMENTS 10 

int main(int argc, const char * argv[]) { 

    int a[N_ELEMENTS] = {1, 2, 3, 2, 0, 5, 1, 6, 0, 1}; 
    int i = 0; 
    while(a[i] < 0 && i<N_ELEMENTS) { 
     i++; 
    } 
    if (a[i] < 0) { 
     printf ("DEBUG: array with only negative numbers. Print the smallest negative number as the sum and we are done.\n"); 
    } 
    int sum_p=0, sum_n = 0; 
    int largest_sum = 0; 
    while (i<N_ELEMENTS) { 
     if (a[i] > 0) { 
      sum_p += a[i]; 
     } 
     else { 
      sum_n += a[i]; 
     } 
     if (sum_p+sum_n > largest_sum) { 
      largest_sum = sum_p + sum_n; 
     } 
     if (sum_p+sum_n <= 0) { 
      // find the next positive number 
      while(a[i] < 0 && i<N_ELEMENTS) { 
       i++; 
      } 
      if (a[i] < 0 || i == N_ELEMENTS) { 
       break; 
      } 
      sum_p = 0; 
      sum_n = 0; 
     } else { 
      i++; 
     } 
    } 
    printf ("DEBUG: The largest consecutive sum = %d\n", largest_sum); 
} 
+0

我不明白wouldnt最大的總和是5,1,6?由於12> 8 – JackVanier

+0

呃,是的,對不起我的壞! – MeChris

+0

所有你需要的是滾動的總和。 –

回答

5

你應該做的是盡一切可能連續三個數字,並從中選擇最好的 類似的東西

int sum = 0; 
int idx = 0 
for(int i=0;i<size-2;i++){ 
    if (A[i]+A[i+1]+A[i+2] > sum){ 
     sum = A[i] + A[i+1] + A[i+2]; 
     idx = i; 
    } 
} 

答案是A [idx],A [idx + 1],A [idx + 2]

+0

在for循環爲什麼你給我的條件我 Cherubim

+0

你是對的,它應該是大小2,而不是我會編輯它 – m7mdbadawy

+0

等待等爲什麼大小2 ..是不是隻是我<大小...如果你給我<大小-2 ..循環將檢查從第一空間只能持續兩個地點..如果和最高的是最後3個? – Cherubim

1

所有你需要的是一個滾動的總和。滑動窗口。您可以在O(n)中線性掃描。

減去剛剛滑出窗口的數字並添加到達的新號碼。跟蹤最大的數額。

1, 2, 3, 2, ... 
-------  sum is 6 
    -------- sum is 6 - 1 + 2 = 7 (biggest sum.. so far) 
     ------- ... 
相關問題