Максимальная сумма всех подмассивов размера k для каждого k = 1..n

Ответ 1

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

вот реализация того же

int maxSum(int arr[], int n, int k) 
{ 
// k must be greater 
if (n < k) 
{ 
   cout << "Invalid"; 
   return -1; 
} 

// Compute sum of first window of size k 
int res = 0; 
for (int i=0; i<k; i++) 
   res += arr[i]; 

// Compute sums of remaining windows by 
// removing first element of previous 
// window and adding last element of  
// current window. 
int curr_sum = res; 
for (int i=k; i<n; i++) 
{ 
   curr_sum += arr[i] - arr[i-k]; 
   res = max(res, curr_sum); 
} 

return res; 
 } 

Сложность времени: O (n) Вспомогательное пространство: O (1)

Источник

Ответ 2

int maxCrossingSum(int arr[], int l, int m, int h) 
{ 
    // Include elements on left of mid. 
    int sum = 0; 
    int left_sum = INT_MIN; 
    for (int i = m; i >= l; i--) 
    { 
        sum = sum + arr[i]; 
        if (sum > left_sum) 
          left_sum = sum; 
    } 

    // Include elements on right of mid 
    sum = 0; 
    int right_sum = INT_MIN; 
    for (int i = m+1; i <= h; i++) 
    { 
        sum = sum + arr[i]; 
        if (sum > right_sum) 
          right_sum = sum; 
    } 

    // Return sum of elements on left and right of mid 
    return left_sum + right_sum; 
} 

// Returns sum of maxium sum subarray in aa[l..h] 
int maxSubArraySum(int arr[], int l, int h) 
{ 
   // Base Case: Only one element 
   if (l == h) 
     return arr[l]; 

   // Find middle point 
   int m = (l + h)/2; 

   /* Return maximum of following three possible cases 
      a) Maximum subarray sum in left half 
      b) Maximum subarray sum in right half 
      c) Maximum subarray sum such that the subarray crosses the midpoint */
   return max(maxSubArraySum(arr, l, m), 
              maxSubArraySum(arr, m+1, h), 
              maxCrossingSum(arr, l, m, h)); 
} 

объяснение

Используя подход "Разделяй и властвуй", мы можем найти максимальную сумму подмассива за время O (nLogn). Ниже приведен алгоритм "Разделяй и властвуй".

1) Разделите данный массив на две половины

2) Вернуть максимум следующих трех

….A) Максимальная сумма подмассива в левой половине (сделать рекурсивный вызов)

….B) Максимальная сумма подмассива в правой половине (сделать рекурсивный вызов)

источник

Ответ 3

Я не думаю, что существует более эффективное решение, чем O (N²), если вы не добавляете никаких других ограничений. Другими словами, нет другого способа решить, что вы нашли субам максимальной суммы, но для изучения всех других подмассивов.

Таким образом, наименее комплексное решение содержит O (N²/2), которое является общим числом смежных подмассивов массива заданной длины N.

Лично я бы реализовал это с помощью подхода динамического программирования. Идея имеет клин частичных результатов и использует их для создания текущих сумм субарей (вместо вычисления всей суммы). В любом случае это дает "только" постоянное ускорение, поэтому сложность O (N²/2) ~ O (N²).

Ниже приведен псевдокод - извините за то, что он не говорит Lua

// here we place temporary results, row by row alternating in 0 or 1
int[2][N] sum_array_buffer
// stores the start of the max subarray
int[N] max_subarray_start
// stores the value
int[N] max_subarray_value

array = {7, 1, 3, 1, 4, 5, 1, 3, 6}
// we initialize the buffer with the array (ideally 1-length subarrays)
sum_array_buffer[1] = array
// the length of subarrays - we can also start from 1 if considered
for k = 1 ; k <= (N); ++k:
    // the starting position fo the sub-array
    for j = 0; j < (N-k+1); ++j:
        sum_array_buffer[k%2][j] = sum_array_buffer[(k+1)%2][j] + array[j+k-1]
        if j == 0 || sum_array_buffer[k%2][j] > max_subarray_value[k]:
            max_subarray_value = sum_array_buffer[k%2][j]
            max_subarray_start[k] = j


for k = 1 ; k <= (N); ++k:
    print(k, max_subarray_value[k])

Graphycally:

Ответ 4

Мы создаем Dequeue, Qi емкости k, который хранит только полезные элементы текущего окна из k элементов. Элемент полезен, если он находится в текущем окне и больше, чем все остальные элементы в левой части окна в текущем окне. Мы обрабатываем все элементы массива один за другим и поддерживаем Qi, чтобы содержать полезные элементы текущего окна, и эти полезные элементы поддерживаются в отсортированном порядке. Элемент спереди Qi является самым большим, а элемент в задней части Qi является самым маленьким из текущего окна.

Ответ 5

Проблема может быть уменьшена до минимальной суммы конвульсий, см. Раздел 2.4 (MCSP) в https://core.ac.uk/download/pdf/84869149.pdf. Поэтому в настоящее время лучшая сложность, которую вы можете ожидать, это, вероятно, O (n ^ 2/polylog (n)).

Ответ 6

    The above question can be solved by O(n).
    Please try this algorithm.
    lets say k=3.
array = {7, 1, 3, 1, 4, 5, 1, 3, 6}
    maxsum=0.
    1)We start with adding 7+1+3 and store sum=11.since sum >maxsum.maxsum=11.
    2)Now since size of k=3,next continuous array is 1+3+1.so how we get this sum??
    remove 7 from sum and add 1 to sum.so now sum is 5.Check if sum>maxsum.
    3)Similarly do for other elements as well.This loop will run until (n-1).''

Пожалуйста, найдите код здесь

 class Program
    {
        static void Main(string[] args)
        {
            int sum=0;
            int max=0;
            int size=9;
           string input="7, 1, 3, 1, 4, 5, 1, 3, 6";
           string[] values=input.Split(',');
           int length=values.Length;
           int k=size-1;
           for(int i=0;i<=k;i++)
           {
             sum=sum+int.Parse(values[i]);
             max=sum;
           }
           for(int j=0;k<length-1;j++)
           {
               ++k;
            sum=(sum-int.Parse(values[j]))+int.Parse(values[k]);
            if(sum>max)
            max=sum;
           }
           Console.WriteLine(max);
        }
    }

Ответ 7

ниже процесс может помочь вам

1) Выберите первые k элементов и создайте самобалансирующееся двоичное дерево поиска (BST) размера k.

2) Запустите цикл для я = 0 до n - k

.....a) Получить максимальный элемент из BST и распечатать его.

.....b) Найдите arr [i] в ​​BST и удалите его из BST.

.....c) Вставить arr [i + k] в BST.

Сложность времени: Сложность времени для шага 1 - O (kLogk). Сложность времени шагов 2 (a), 2 (b) и 2 (c) равна O (Logk). Поскольку этапы 2 (a), 2 (b) и 2 (c) находятся в цикле, который работает n-k + 1 раз, временная сложность полного алгоритма равна O (kLogk + (n-k + 1) * Logk) который также может быть записан как O (nLogk).