Максимална кружна сума низа


Ниво тешкоће Средњи
Често питани у амазонка фацебоок ЛинкедИн Тво Сигма Убер
Ред

Изјава о проблему

У задатку са максималном кружном сумом низа дали смо поредак целих бројева поређаних у круг, пронађите максимални збир узастопних бројева у кружном низу.

Пример

Улазни

арр [] = {13, -17, 11, 9, -4, 12, -1}

Излаз

40

Објашњење

Овде је збир = 11 + 9 + -4 + 12 + -1 + 13

Улазни

арр [] = {7, 9, -11, -2, 2, 7, -1, 6}

Излаз

30

Објашњење

Овде је збир = 2 + 7 + -1 + 6+ 7 + 9

Улазни

арр [] = {-17, -2, 1, -10, 2, 3, 7, 9}

Излаз

21

Објашњење

Овде је збир = 2 + 3 + 7 + 9

Алгоритам за максималну суму кружног подниза

У задатку са максималном кружном сумом низа имамо два услова. Први услов је да су сви елементи у суседном поднизу. А други услов је да неки елементи буду са почетка, а неки са краја низа. За боље разумевање погледајте доњи алгоритам-

1) Елементи који доприносе максималном збиру распоређени су тако да нема умотавања. Као у примеру (ц)

2) Елементи који доприносе максималном збиру распоређени су тако да постоји омотавање. Као у примеру (а, б).

3) За случај 1 користимо стандард Кадане алгоритам да би се пронашла максимална сума низа.

4) За случај 2 мењамо умотавање у непаковање.

  • Збир свих елемената чувамо у низу.
  • Промените предзнак свих елемената додајући у збир.
  • За нови низ са обрнутим знаковима поново примените алгоритам кадане на овај нови низ.
  • Укупан збир додајте новом збиру кадане.
  • Упоредите ову суму са почетном сумом кадане (пре него што обрнете знакове), максималан поврат међу њима.

Имплементација

Програм Ц ++ за максималну суму кружног подмреже

#include <bits/stdc++.h>
using namespace std;
// Standard Kadane's algorithm to find maximum subarray sum
int kadane(int array[], int n)
{
    int max_so_far = 0, max_ending_here = 0;
    for (int i = 0; i < n; i++)
    {
        max_ending_here = max_ending_here + array[i];
        if (max_ending_here < 0)
            max_ending_here = 0;
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
    }
    return max_so_far;
}
 
//function to find maximum circular subarray sum
int MaxSumCircular(int array[], int n)
{
    //Max subarray sum in the given array
    int kadane_sum = kadane(array, n);
    //wrap_sum is sum of all elements in the array
    int wrap_sum = 0;
    //find sum of all elements in the array
    //invert signs of all elements in the array
    for (int i=0; i<n; i++)
    {
        wrap_sum += array[i]; 
        array[i] = -array[i];
    }
    //update wrap_sum by add to new Max subarray sum
    wrap_sum = wrap_sum + kadane(array, n);
    //Return the maximum of them
    if(wrap_sum > kadane_sum)
    {
      return wrap_sum;
    }
    else
    {
      return kadane_sum;
    }
}
  
//Main function
int main()
{
    int input_array[] = {7, 9, -11, -2, 2, 7, -1, 6};
    int size = sizeof(input_array)/sizeof(int);
    cout<<"Maximum circular subarray sum: "<<MaxSumCircular(input_array,size)<<endl;
    return 0;
}

Јава програм за максималну кружну суму низа

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int kadane(int array[], int n)
    {
        int max_so_far = 0, max_ending_here = 0;
        for (int i = 0; i < n; i++)
        {
            max_ending_here = max_ending_here + array[i];
            if (max_ending_here < 0)
                max_ending_here = 0;
            if (max_so_far < max_ending_here)
                max_so_far = max_ending_here;
        }
        return max_so_far;
    }
    public static int MaxSumCircular(int array[], int n)
    {
        //Max subarray sum in the given array
        int kadane_sum = kadane(array, n);
        //wrap_sum is sum of all elements in the array
        int wrap_sum = 0;
        //find sum of all elements in the array
        //invert signs of all elements in the array
        for (int i=0; i<n; i++)
        {
            wrap_sum += array[i]; 
            array[i] = -array[i];
        }
        //update wrap_sum by add to new Max subarray sum
        wrap_sum = wrap_sum + kadane(array, n);
        //Return the maximum of them
        if(wrap_sum > kadane_sum)
        {
          return wrap_sum;
        }
        else
        {
          return kadane_sum;
        }
    } 
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int ans = MaxSumCircular(arr,n);
        System.out.println("Maximum circular subarray sum: " + ans);
    } 
}
8
7 9 -11 -2 2 7 -1 6
Maximum circular subarray sum: 30

Анализа сложености

Сложеност времена

НА) где је Н број елемената присутних у датом низу. Овде користимо алгоритам кадане који нас доводи до линеарне временске сложености.

Сложеност простора

О (1) јер резултат израчунавамо користећи неколико променљивих. Овде користимо оптимални алгоритам простора кадане.

Референце