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

Ответ 1

Я предполагаю, что вы используете алгоритм 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;

Ответ 2

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

Решает проблему, используя Kadane Algorithem.

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

Ответ 3

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

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

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

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

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

Ответ 4

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

Ответ 5

Для данной задачи, Мы применим алгоритм кадана, и мы также найдем подмножество, которое будет иметь максимальное отрицательное значение. Если будет удалено максимальное отрицательное значение, которое даст сумму оставшегося массива в круговом порядке. Если эта сумма больше максимальной суммы, тогда максимальная сумма будет суммой в круговом порядке. Сложность для алгоритма 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;

}

Ответ 6

Исправить код, основанный на идея nikhil: элементы минимальной суммы субаммы не могут появляться в финальной сумме суммирования или не максимальной суммы -array.

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;
}