Найти непрерывную часть массива, чтобы сумма элементов была максимальной - C (СИ)
Формулировка задачи:
массив из случайных целых чисел от -1000 до 1000. задача найти непрерывную часть этого массива чтобы сумма элементов была максимальной
Решение задачи: «Найти непрерывную часть массива, чтобы сумма элементов была максимальной»
textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int *build_arr(unsigned lenght, int max, int min);
void print_arr(int *ptr, unsigned lenght);
void print_sequence(int *ptr, unsigned lenght);
int main(void)
{
srand(time(NULL));
unsigned arrlen = 15;
int *arr = build_arr(arrlen, 1000, -1000);
print_arr(arr, arrlen);
print_sequence(arr,arrlen);
free (arr);
return 0;
}
int *build_arr(unsigned lenght, int max, int min) {
int *ptr = malloc(sizeof(int)*lenght);
if (ptr == NULL) {
puts ("out of memory!");
exit (1);
}
int *pos = ptr;
while ((pos-ptr) < lenght) {
*pos = rand() % (max * 2) + 1 + min;
pos++;
}
return ptr;
}
void print_arr(int *ptr, unsigned lenght) {
while (lenght--)
printf("%i ", *ptr++);
putchar('\n');
}
void print_sequence(int *ptr, unsigned lenght) {
long max[2][lenght];
int *pos;
int i;
for (i=0; i<lenght; i++) {
pos = &ptr[i];
long temp_max = 0;
long counter = 0;
while (pos < (&ptr[0] + lenght)) {
counter += (*pos);
if (counter > temp_max)
temp_max = counter;
++pos;
}
max[0][i] = temp_max;
pos = &ptr[i-1];
temp_max? (counter = temp_max): (counter = *(pos+1));
while (pos >= &ptr[0]) {
counter += (*pos);
if (counter > temp_max)
temp_max = counter;
--pos;
}
max[1][i] = temp_max;
}
int number = 0;
pos = (int*)&max[1][0];
for (i=0; i<lenght; i++)
if (*pos < max[1][i]) {
pos = (int*)&max[1][i];
number = i;
}
while (1) {
printf ("%i ", ptr[number]);
if (max[1][number] == max[1][number+1])
number++ ;
else
break;
}
putchar('\n');
}
Объяснение кода листинга программы
- Название: main Описание: Главная функция программы, инициализирует генератор случайных чисел, создает массив заданной длины с случайными числами, выводит этот массив на экран, а затем выводит непрерывную последовательность элементов с максимальной суммой.
- Название: build_arr Описание: Функция для создания массива заданной длины с случайными числами в указанном диапазоне.
- Название: print_arr Описание: Функция для вывода на экран элементов массива через пробел.
- Название: print_sequence Описание: Функция для поиска непрерывной последовательности элементов массива с максимальной суммой. Использует два подмассива для отслеживания максимальной суммы, обновляя их при переходе к следующему элементу. При достижении конца массива, начинает проверку предыдущих элементов, пока не найдет непрерывную последовательность с максимальной суммой.
- Название: number Описание: Локальная переменная в функции print_sequence, используется для отслеживания индекса текущего элемента непрерывной последовательности.
- Название: max_counter Описание: Локальная переменная в функции print_sequence, используется для отслеживания текущей максимальной суммы.
- Название: temp_max Описание: Локальная переменная в функции print_sequence, используется для временного хранения текущей максимальной суммы.
- Название: counter Описание: Локальная переменная в функции print_sequence, используется для отслеживания суммы текущих элементов.
- Название: pos Описание: Локальная переменная в функции print_sequence, используется для перемещения по массиву при поиске непрерывной последовательности.
- Название: ptr Описание: Локальная переменная в функции print_sequence, используется для обращения к элементам массива.