Упражнения C: Найти максимальную круговую сумму подмассива для данного массива

Массив C: упражнение 51 с решением

Напишите программу на C, чтобы найти максимальную круговую сумму подмассива для данного массива.

Иллюстрированная презентация:

Пример решения:

Код C:

#include <stdio.h>
int kadane(int arr1[], int n);
int SumOfMxCircur(int arr1[], int n)
{
   int maxKadaneSum  = kadane(arr1, n);
   int maxWrap = 0, i;
   for (i=0; i<n; i++)
   {
        maxWrap += arr1[i]; 
        arr1[i] = -arr1[i];  
   }
   maxWrap = maxWrap + kadane(arr1, n);
   return (maxWrap > maxKadaneSum)? maxWrap: maxKadaneSum;
}
int kadane(int arr1[], int n)
{
    int maxUpto  = 0, maxAtPos = 0;
    int i;
    for (i = 0; i < n; i++)
    {
        maxAtPos = maxAtPos + arr1[i];
        if (maxAtPos < 0)
            maxAtPos = 0;
        if (maxUpto < maxAtPos)
            maxUpto = maxAtPos;
 }           
   return maxUpto;
}
 
int main()
{
      int arr1[] =  {10, 8, -20, 5, -3, -5, 10, -13, 11};
    int n = sizeof(arr1)/sizeof(arr1[0]);
	int i;
 //------------- print original array ------------------	
	printf("The given array is :  ");
	for(i = 0; i < n; i++)
	{
	printf("%d  ", arr1[i]);
    } 
	printf("\n");
//------------------------------------------------------ 	
    printf("The maximum circular sum in the above array is:  %d\n", SumOfMxCircur(arr1, n));
    return 0;
}

Пример вывода:

 Данный массив: 10 8 -20 5 -3 -5 10 -13 11  
Максимальная круговая сумма в указанном массиве: 29

Блок - схема:

Редактор кода программирования C:

Улучшите этот пример решения и опубликуйте свой код через Disqus.

Previous: написать программу на C для печати матрицы в виде спирали.
Далее: Напишите программу на C, чтобы подсчитать количество треугольников, которые могут быть взяты из заданного массива.