C数组中3个连续数字的最大和

Question

我正在学习 C，我的老师给我布置了一个任务，但我卡住了。数组中有 10 个正数，我需要找到 3 个总和最大的连续数。我在网上找到了这个解决方案，但是如何找到 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);
}

Answer 1

你应该做的是尝试所有可能的连续三个数字，然后从中选择最好的类似的东西

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]

Answer 2

您只需要一个滚动总和。一个滑动window。您可以在 O(n) 中线性扫描。

减去刚从 window 中滑出的数字，然后加上新的数字。跟踪最大的总和。

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

C数组中3个连续数字的最大和

C largest sum of 3 consecutive numbers from array

c

arrays

numbers

sum