Определить, какие k подряд идущих элементов массива имеют максимальную сумму - C (СИ)
Формулировка задачи:
Дан целочисленный массив, размер которого не превышает 1000000, и число k, которое меньше или равно длине массива. Составьте программу maxk.c, определяющую, какие k подряд идущих элементов массива имеют максимальную сумму.
Программа должна считывать из стандартного потока ввода размер массива, его элементы и число k, а затем выводить в стандартный поток вывода максимальную сумму k подряд идущих элементов массива.
В программе запрещается обращаться к одному и тому же элементу массива более двух раз, а также объявлять какие бы то ни было вспомогательные массивы.
Решение задачи: «Определить, какие k подряд идущих элементов массива имеют максимальную сумму»
textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int main(int argc, char *argv[])
{
long int *Arr;
long int n,k,s,smax,i,j,p;
printf("n=");
scanf("%d",&n);
Arr=(long int*) calloc(n,sizeof(long int));
for (i=0; i<n; i++) {printf("A[%d]=",i); scanf("%d",&Arr[i]);}
printf("\nk=");
scanf("%d",&k);
s=0;
for (i=0; i<k; i++) s=s+Arr[i];
smax=s;
j=0;
p=k;
while(1)
{
if (p >= n) break;
s=s-Arr[j++];
s=s+Arr[p++];
if (s>smax) smax=s;
}
printf("\n\nmax=%d\n",smax);
free(Arr);
system("PAUSE");
return 0;
}
Объяснение кода листинга программы
В этом коде:
- Считывается из стандартного ввода количество элементов массива n
- Массив Arr инициализируется размером n элементов
- Считываются значения элементов массива Arr из стандартного ввода
- Считывается значение k
- Находится сумма первых k элементов массива Arr и сохраняется в переменной s
- Находится максимальная сумма среди всех возможных подмассивов длиной k элементов
- Выводится на экран максимальная сумма
- Освобождается память, выделенная под массив Arr
- Останавливается программа до тех пор, пока пользователь не нажмет любую клавишу Код решает задачу поиска максимальной суммы k подряд идущих элементов массива.