максимальная непрерывная сумма в кольцевом буфере

Question

У меня есть программа для определения наибольшей непрерывной суммы в массиве, но я хочу расширить ее для работы с круговыми массивами. Есть ли более простой способ сделать это, чем удвоить один массив и вызвать мою функцию, чтобы найти наибольшую сумму по всем массивам n-длины в массиве 2n-длины?

Answer 1

См. Следующую ссылку:

Решает проблему с помощью Кадане Алгоритема.

http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/

Answer 2

Я думаю, что решение @spinning_plate неверно.Можете ли вы проверить это для данных случаев.

int arr [] = {-3, 6, 2, 1, 7, -8, 13, 0};

Ваш подход возвращается21.

Фактическое решение может начинаться с 6-го индекса (т. Е. 13 значения) .. и заканчиваться 4-м индексом (т. Е. 7 значения).Поскольку массив является круглым, мы можем взять непрерывный ряд от 6-го индекса до 7-го индекса и от 0-го индекса до 4-го индекса.

Фактический ответ для приведенного выше случая: 26

Answer 3

Для данной задачи, мы применим алгоритм Кадане, и мы также найдем подмножество, которое будет иметь максимальное отрицательное значение. Если максимальное отрицательное значение будет удалено, это даст сумму оставшегося массива в круговом порядке.больше максимальной суммы, тогда максимальная сумма будет суммой в круговом порядке.Сложность алгоритма O (n).

Eg:- arr[i]={10,-3,-4,7,6,5,-4,-1}
      Ans:  max_sum=7+6+5+(-4)+(-1)+10
            Removed_set={-3,-4}
int find_maxsum(int arr[],int n)
{
 int i=0;
 int total=0;
 int maxa=0;
 int mini=0;
 int min_sum=0;
 int max_sum=0;


 while(i<n) 
  {
    maxa=maxa+arr[i];
    total=total+arr[i];
    mini=mini+arr[i];

   if(maxa>max_sum)
     max_sum=maxa; 
   if(mini<min_sum)
     min_sum=mini;
   if(maxa<0)
     maxa=0;
   if(mini>=0)
    mini=0;
}
if(total-min_sum>max_sum)
   max_sum=total-min_sum;
 return max_sum;

}

Answer 4

Ну, вам не нужно фактически удваивать массив. Вы можете просто эмулировать его, индексируя существующий массив по модулю n или просто повторяя его дважды. В зависимости от размера вашего массива и поведения кэша, он должен быть в два раза медленнее, чем алгоритм для некруглого массива.

Answer 5

Правильный код, основанный на идее nikhil : элементы подмассива с минимальной суммой не могут появиться в окончательном подмассиве с минимальной суммой переноса.

public int maxSum(int[] arr) {
    if (arr.length == 0) return 0;

    int sum = 0;
    int min = Integer.MAX_VALUE;
    int eix = 0;
    for (int i = 0; i < arr.length; i++) {
        sum = sum + arr[i] < arr[i] ? sum + arr[i] : arr[i];
        if (sum < min) {
            min = sum;
            eix = i;
        }
    }
    int max = 0;
    sum = 0;
    for (int i = eix; i < arr.length + eix; i++) {
        int ix = i < arr.length ? i : i - arr.length;
        sum = sum + arr[ix] > arr[ix] ? sum + arr[ix] : arr[ix];
        max = max > sum ? max : sum;
    }

    return max;
}

Answer 6

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

max_start=0; max_end =0; maxv = 0; sum 0;
for i in range(arr):
    sum+= arr[i];
    if sum<0:
       sum=0; max_start =i;
    if maxv<sum:
       maxv=sum; max_end = i;

#seocnd pass
for i in range(max_start):
    sum+= arr[i];
    if sum<0:
       break;
    if maxv<sum:
       maxv=sum;max_end = i;