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