Найти непрерывную часть массива, чтобы сумма элементов была максимальной - 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');
}

Объяснение кода листинга программы

  1. Название: main Описание: Главная функция программы, инициализирует генератор случайных чисел, создает массив заданной длины с случайными числами, выводит этот массив на экран, а затем выводит непрерывную последовательность элементов с максимальной суммой.
  2. Название: build_arr Описание: Функция для создания массива заданной длины с случайными числами в указанном диапазоне.
  3. Название: print_arr Описание: Функция для вывода на экран элементов массива через пробел.
  4. Название: print_sequence Описание: Функция для поиска непрерывной последовательности элементов массива с максимальной суммой. Использует два подмассива для отслеживания максимальной суммы, обновляя их при переходе к следующему элементу. При достижении конца массива, начинает проверку предыдущих элементов, пока не найдет непрерывную последовательность с максимальной суммой.
  5. Название: number Описание: Локальная переменная в функции print_sequence, используется для отслеживания индекса текущего элемента непрерывной последовательности.
  6. Название: max_counter Описание: Локальная переменная в функции print_sequence, используется для отслеживания текущей максимальной суммы.
  7. Название: temp_max Описание: Локальная переменная в функции print_sequence, используется для временного хранения текущей максимальной суммы.
  8. Название: counter Описание: Локальная переменная в функции print_sequence, используется для отслеживания суммы текущих элементов.
  9. Название: pos Описание: Локальная переменная в функции print_sequence, используется для перемещения по массиву при поиске непрерывной последовательности.
  10. Название: ptr Описание: Локальная переменная в функции print_sequence, используется для обращения к элементам массива.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

13   голосов , оценка 3.538 из 5
Похожие ответы