Максимальный подмассив в КОЛЬЦЕВОМ массиве , Нужно найти первый и последний элемент в кольцевом массиве, сумма элементов между которыми максимальна.

[getch]

Приветствую!

В одномерном числовом массиве нужно найти максимальный подмассив. Но в отличие от известной задачи нумерация элементов закольцована: после последнего элемента идет первый и т.д.

Примеры для самопроверки:
{5, -4, -1, 7, -1, 6, -2, -1, 1, -4} выделенная искомая сумма 12.

Этот же массив, только начало с другого элемента
{-1, 6, -2, -1, 1, -4, 5, -4, -1, 7} выделенная искомая сумма 12.

Снова этот же массив, но с другим началом
{6, -2, -1, 1, -4, 5, -4, -1, 7, -1} выделенная искомая сумма 12.


Классическое решение для некольцевого массива имеет O(n). Помогите найти оптимальный вариант для кольцевого случая.
Спасибо!

[MIF]

При данных ограничениях максимальный подмассив всегда равен массиву.

[getch]

Цитата MIF @ 09.10.18, 12:28

При данных ограничениях максимальный подмассив всегда равен массиву.

Максимальный подмассив будет равен массиву только в случае, если все элементы исходного массива положительны.
Видимо, я плохо сформулировал. Максимальный подмассив - это подмассив с максимальной суммой элементов.
Разница от классической постановки задачи - исходный массив является кольцевым.

[Akina]

Добавляем в хвост массива его копию без последнего элемента.
Устанавливаем ограничение на длину подмассива не более исходной длины массива.
Решаем стандартную задачу. Сложность O(2n) = O(n).

Применительно к показанному примеру

{5, -4, -1, 7, -1, 6, -2, -1, 1, -4} => {5, -4, -1, 7, -1, 6, -2, -1, 1, -4, 5, -4, -1, 7, -1, 6, -2, -1, 1}
{-1, 6, -2, -1, 1, -4, 5, -4, -1, 7} => {-1, 6, -2, -1, 1, -4, 5, -4, -1, 7, -1, 6, -2, -1, 1, -4, 5, -4, -1}
{6, -2, -1, 1, -4, 5, -4, -1, 7, -1} => {6, -2, -1, 1, -4, 5, -4, -1, 7, -1, 6, -2, -1, 1, -4, 5, -4, -1, 7}

Сообщение отредактировано: Akina - 09.10.18, 13:43

[getch]

Цитата Akina @ 09.10.18, 13:37

Добавляем в хвост массива его копию без последнего элемента.
Устанавливаем ограничение на длину подмассива не более исходной длины массива.
Решаем стандартную задачу. Сложность O(2n) = O(n).

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

int Res = 0;
int Left = -1;
int Right = -1;
 
int Sum = 0;    
int MinusPos = -1;
    
const int Size2 = Size << 1;
 
for (int i = 0; i < Size2; i++)
{
  const int Pos = i % Size;
  
  if (Pos != Left) // ограничение на длину подмассива
  {
    Sum += Array[Pos];
  
    if (Sum > Res)
    {
        Res = Sum;
        
        Left = MinusPos + 1;
        Right = i;
    }
  
    if (Sum < 0)
    {
        Sum = 0;
        
        MinusPos = Pos;
    }        
  }
  else
    break;              
}
 
Right %= Size;

Результат на {-1, 6, -2, -1, 1, -4, 5, -4, -1, 7} - Left = 1, Right = 9, Res = 7 - сумма.

Как правильно задать ограничение на длину?

[Akina]

Цитата getch @ 09.10.18, 13:57

задать ограничение на длину подмассива не выходит

В стандартный метод надо внести два измнения.
Первое - накапливать суммы, начиная с любого потенциального начала последовательности.
Второе - фиксировать макс. сумму для каждой последовательности, достигшей макс. длины.
Правда, при этом сложность возрастёт до O(m*n), но зато элементарно в реализации.

[amk]

Цитата getch @ 09.10.18, 13:57

Но задать ограничение на длину подмассива не выходит.

И не выйдет. Классический алгоритм не приспособлен для такого ограничения в принципе.
Однако, немного подумав, можно заметить, что в задаче возможны только два типа решений:
одно совпадает с линейным решением,
а второе является дополнением к такой же задаче поиска, но минимального интервала.
Ко второму варианту классический алгоритм приспосабливается элементарно сменой знаков значений в массиве или сменой операторов сравнения.
Обе задачи можно решать в одном цикле прохода по массиву, параллельно считая сумму массива (чтобы посчитать потом дополнение).

[getch]

Цитата amk @ 09.10.18, 16:40

Цитата getch @ 09.10.18, 13:57

Но задать ограничение на длину подмассива не выходит.

И не выйдет. Классический алгоритм не приспособлен для такого ограничения в принципе.
Однако, немного подумав, можно заметить, что в задаче возможны только два типа решений:
одно совпадает с линейным решением,
а второе является дополнением к такой же задаче поиска, но минимального интервала.
Ко второму варианту классический алгоритм приспосабливается элементарно сменой знаков значений в массиве или сменой операторов сравнения.
Обе задачи можно решать в одном цикле прохода по массиву, параллельно считая сумму массива (чтобы посчитать потом дополнение).

Действительно, получилось!

// Поиск максимального отрезка в кольце
template <typename T>
T GetAnsRing( T &Array[], int &Left, int &Right )
{    
  T SumMin = 0;    
  T AnsMin = 0;
  int   LeftMin = 0;
  int RightMin = 0;
  int   MinusPos = -1;
 
  T SumMax = 0;
  T AnsMax = 0;
  int   LeftMax = 0;
  int RightMax = 0;
  int PositivePos = -1;
  
  T SumArray = 0;
 
  const int Size = ::ArraySize(Array);
        
  for (int i = 0; i < Size; i++)
  {
    SumArray += Array[i];      
    SumMax += Array[i];
    SumMin += Array[i];
  
    if (SumMax > AnsMax)
    {
        AnsMax = SumMax;
        
        LeftMax = MinusPos + 1;
        RightMax = i;
    }
    else if (SumMax < 0)    
    {
        SumMax = 0;
        
        MinusPos = i;
    }
    
    if (SumMin < AnsMin)
    {
        AnsMin = SumMin;
        
        LeftMin = PositivePos + 1;
        RightMin = i;
    }
    else if (SumMin > 0)    
    {
        SumMin = 0;
        
        PositivePos = i;
    }  
  }
  
  const T AnsMax2 = SumArray - AnsMin;
  const bool Reverse = (AnsMax2 > AnsMax);
  
  Left = Reverse ? (RightMin + 1) % Size : LeftMax;
  Right = Reverse ? (LeftMin + Size - 1) % Size : RightMax;    
 
  return(Reverse ? AnsMax2 : AnsMax);
}

Спасибо!

[getch]

Здравствуйте. Следующая задача является развитием задачи, что была решена в этой ветке несколько лет назад.

В числовом (положительные и отрицательные числа) массиве нужно найти k непересекающихся подмассивов, общая сумма элементов в которых максимальна. Идеально, если задача будет решаться для зацикленного массива.

Выше был предложен линейный алгоритм для k = 1.

Интуитивно понимаю, что сложность должна быть O(k*n). Но получается громоздко, до реализации еще не допилил. Все время всплывают ситуации, которые не учел.
Исходил из того, что если есть решение для k, то из него линейно можно получить решение для k+1.

Несколько примеров того, что нужно получить.

{1, 2, 3, -5, 1, 2, 3, -10, 1, 2, 3, -20}, k = 0
{1, 2, 3, -5, 1, 2, 3, -10, 1, 2, 3, -20}, k = 1, SumMax = 7
{1, 2, 3, -5, 1, 2, 3, -10, 1, 2, 3, -20}, k = 2, SumMax = 7 + 6
{1, 2, 3, -5, 1, 2, 3, -10, 1, 2, 3, -20}, k = 3, SumMax = 6 + 6 + 6

{1, 2, 3, -5, 1, 2, 3, -10, 1, 1, 2, -20}, k = 0
{1, 2, 3, -5, 1, 2, 3, -10, 1, 1, 2, -20}, k = 1, SumMax = 7
{1, 2, 3, -5, 1, 2, 3, -10, 1, 1, 2, -20}, k = 2, SumMax = 6 + 6
{1, 2, 3, -5, 1, 2, 3, -10, 1, 1, 2, -20}, k = 3, SumMax = 6 + 6 + 4

Просьба помочь. Возможно, уже есть известное решение.

[getch]

Цитата getch @ 26.07.23, 10:53

В числовом (положительные и отрицательные числа) массиве нужно найти k непересекающихся подмассивов, общая сумма элементов в которых максимальна. Идеально, если задача будет решаться для зацикленного массива.

Обнаружил, что это стандартная задача, к решению которой сводилась задача "Пингвиноведение" со всеросса 2015.

Были даны такие комментарии по ней.

Цитата

• Пусть нам необходимо выбрать в массиве k непересекающихся отрезков с максимальной суммой.
• Для k = 1 необходимо найти один отрезок с максимальной суммой, это — стандартная задача.
• Будем строить ответ инкрементально: пусть мы уже построили k отрезков, научимся строить k+1.
• Утверждается, что выгодно либо добавить отрезок, который не пересекается ни с одним из уже выбранных, либо следует разбить один из выбранных отрезков на два, «вырезав» из него некоторый подотрезок.
• Необходимо на отрезке уметь искать подотрезок с максимальной суммой, это — стандартная задача на дерево отрезков.
• Так на каждом шаге есть O(k) вариантов действий, то мы уже получили решение за O(k^2+nlog n).
• Для оптимизации решения следует заметить, что наши возможности слабо изменяются при перестроении ответа: у нас, возможно, добавляются три новых возможных отрезка, и удаляется один из возможных.
• Таким образом, мы можем использовать PriorityQueue или Set для выбора оптимального действия на каждом шаге.

Есть даже исходник решения той задачи с соревнований, но для меня, как не знакомого с теорией алгоритмов, темный лес, как выделить из исходника решение стандартной задачи.

[getch]

Цитата getch @ 26.07.23, 10:53

Интуитивно понимаю, что сложность должна быть O(k*n).

Сделал.

#define MACROS_ANS(A, B, C, D) \
  Sum##D += A;                 \
                               \
  if (Sum##D C Ans##D)         \
  {                            \
    Ans##D = Sum##D;           \
                               \
    Left##D = Pos##D + 1;      \
    Right##D = B;              \
  }                            \
  else if (!(Sum##D C 0))      \
  {                            \
    Sum##D = 0;                \
                               \
    Pos##D = B;                \
  }
 
template <typename T>
T GetAnsRing( const T &Array[], int &Left, int &Right )
{
  T SumMin = 0;
  T AnsMin = 0;
  int LeftMin = 0;
  int RightMin = 0;
  int PosMin = -1;
 
  T SumMax = 0;
  T AnsMax = 0;
  int LeftMax = 0;
  int RightMax = 0;
  int PosMax = -1;
 
  T SumArray = 0;
 
  const int Size = ::ArraySize(Array);
 
  for (int i = 0; i < Size; i++)
  {
    const T Value = Array[i];
 
    SumArray += Value;
 
    MACROS_ANS(Value, i, >, Max)
    MACROS_ANS(Value, i, <, Min)
  }
 
  AnsMin = SumArray - AnsMin;
 
  const bool Reverse = (AnsMin > AnsMax);
 
  Left = Reverse ? (RightMin + 1) % Size : LeftMax;
  Right = Reverse ? (LeftMin + Size - 1) % Size : RightMax;
 
  return(Reverse ? AnsMin : AnsMax);
}
 
template <typename T>
T CalcInterval( const T &Array[], int &LeftNew, int &RightNew, const uchar &Mask[], int &i, const int &Size )
{
  T SumNew = 0;
  T AnsNew = 0;
  int PosNew = i - 1;
 
  const int End = i;
  const int PrevMask = Mask[i];
 
  if (PrevMask)
    do
    {
      MACROS_ANS(Array[i], i, <, New)
 
      if (++i == Size)
        i = 0;
 
    } while ((i != End) && (Mask[i] == PrevMask));
  else
    do
    {
      MACROS_ANS(Array[i], i, >, New)
 
      if (++i == Size)
        i = 0;
 
    } while ((i != End) && (Mask[i] == PrevMask));
 
  LeftNew %= Size;
 
  return(PrevMask ? -AnsNew : AnsNew);
}
 
template <typename T>
T Step( const T &Array[], int &Left, int &Right, const uchar &Mask[], const int From )
{
  const int Size = ArraySize(Array);
 
  int LeftNew;
  int RightNew;
 
  T Ans = 0;
 
  int Pos = From;
 
  do
  {
    const T AnsNew = CalcInterval(Array, LeftNew, RightNew, Mask, Pos, Size);
 
    if (AnsNew > Ans)
    {
      Left = LeftNew;
      Right = RightNew;
 
      Ans = AnsNew;
    }
  } while (Pos != From);
 
  return(Ans);
}
 
void IntervalReverse( uchar &Mask[], const int &Left, const int &Right )
{
  const uchar Value = (uchar)(1 - Mask[Left]);
 
  if (Left <= Right)
    ArrayFill(Mask, Left, Right - Left + 1, Value);
  else
  {
    ArrayFill(Mask, Left, ArraySize(Mask) - Left, Value);
    ArrayFill(Mask, 0, Right + 1, Value);
  }
}
 
template <typename T>
T Solve( const T &Array[], uchar &Mask[], const int Amount = 1 )
{
  T Ans = 0;
 
  ArrayResize(Mask, ArraySize(Array));
 
  if (Amount > 0)
  {
    ArrayInitialize(Mask, 0);
 
    int Left;
    int Right;
 
    Ans = GetAnsRing(Array, Left, Right);
    IntervalReverse(Mask, Left, Right);
 
    const int From = Left;
    T AnsAdd = 0;
 
    for (int i = 1; (i < Amount) && (bool)(AnsAdd = Step(Array, Left, Right, Mask, From)); i++)
    {
      Ans += AnsAdd;
 
      IntervalReverse(Mask, Left, Right);
    }
  }
  else
  {
    ArrayInitialize(Mask, 1);
 
    for (uint i = ArraySize(Array); (bool)i--;)
      Ans += Array[i];
  }
 
  return(Ans);
}
 
 
template <typename T>
void PrintResult( const T &Array[], const uchar &Mask[] )
{
  T ArrayOut[];
 
  for (uint i = ArrayCopy(ArrayOut, Array); (bool)i--;)
    if (!Mask[i])
      ArrayOut[i] = 0;
 
  ArrayPrint(ArrayOut);
}
 
void OnStart()
{
  int Array[] = {1, 2, 3, -5, 1, 2, 3, -10, 1, 1, 2, -20};
  uchar Mask[];
 
  for (int i = 0; i < 5; i++)
  {
    Print("\nIntervals = " + (string)i + ", Sum = " + (string)Solve(Array, Mask, i));
    PrintResult(Array, Mask);
  }
}

[Feldsher]

Если случайные значения в массиве мы должны перебирать комбинации элементов массива, или другие решения предлагаются?

[getch]

Цитата Feldsher @ 27.07.23, 19:45

Если случайные значения в массиве мы должны перебирать комбинации элементов массива, или другие решения предлагаются?

Предложенное решение работает для любых массивов, где есть хотя бы один положительный элемент.