Найти непрерывную часть массива, чтобы сумма элементов была максимальной - 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, используется для обращения к элементам массива.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д