Збир минималних и максималних елемената свих подређаја величине к  


Ниво тешкоће Тежак
Често питани у БитеДанце Цапитал Оне ЦоупонДуниа Датабрицкс гоогле Твилио иандек
Ред Ред Клизни прозор

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

Проблем „Збир минималних и максималних елемената свих подређаја величине к“ наводи да вам је дат низ који садржи позитивне и негативне целобројне вредности, пронађите зброј минималних и максималних елемената свих под низова величине к.

Примери  

arr[] = {5, 9, 8, 3, -4, 2, 1, -5}
k = 4
17

Објашњење
Сви под-низови величине 4 су,
{5, 9, 8, 3}: мин + мак = 9 + 3 = 12
{9, 8, 3, -4}: мин + мак = -4 + 9 = 5
{8, 3, -4, 2}: мин + мак = -4 + 8 = 4
{3, -4, 2, 1}: мин + мак = -4 + 3 = -1
{-4, 2, 1, -5}: мин + мак = -5 + 2 = -3

Збир минималних и максималних елемената свих подређаја величине кПин

arr[] = {1, -1, 2, -2, 3, -3}
k = 2
2

Објашњење
Сви под-низови величине 2 су,
{1, -1}: мин + макс = -1 + 1 = 0
{-1, 2}: мин + мак = -1 + 2 = 1
{2, -2}: мин + макс = -2 + 2 = 0
{-2, 3}: мин + мак = -2 + 3 = 1
{3, -3}: мин + макс = -3 + 3 = 0

Приступ  

Наивни приступ

Пређите све поднизове величине к да бисте пронашли њихове минималне и максималне елементе и одштампајте збир.

  1. Иницијализујте променљиву суму као 0.
  2. Покрените петљу за и једнако 0 до (н - к), где је н укупан број елемената у датом поредак. Сваки и делује као почетна тачка под-низа величине к.
  3. Покрените угнежђену петљу за ј = и до (и + к) (није укључено), ова петља представља под-низ величине к. Пређите ову под-матрицу и пронађите минимум и максимум елемената, нека буду мин и мак респективно.
  4. Додај (мин + максимум) збиру.
  5. На крају преласка, повратна сума.
Види такође
Редослед приоритета у Ц ++

где је н укупан број елемената у датом низу.

Јава код за проналажење збира минималних и максималних елемената свих подређаја величине к

class SumOfMinimumAndMaximumElementsOfAllSubarraysOfSizeK {
    private static int sumOfMinMax(int[] arr, int k) {
        int n = arr.length;
        // initialize sum as 0
        int sum = 0;

        // Traverse all the subarray of size k one by one
        for (int i = 0; i <= n - k; i++) {
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            // traverse the current subarray and find the min and max
            for (int j = i; j < i + k; j++) {
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);
            }

            // add (min + max) to the sum
            sum += (min + max);
        }

        return sum;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 9, 8, 3, -4, 2, 1, -5};
        int k1 = 4;
        System.out.println(sumOfMinMax(arr1, k1));

        // Example 2
        int arr2[] = new int[]{1, -1, 2, -2, 3, -3};
        int k2 = 2;
        System.out.println(sumOfMinMax(arr2, k2));
    }
}
17
2

Ц ++ код за проналажење Збир минималних и максималних елемената свих подређаја величине к

#include<bits/stdc++.h> 
using namespace std; 

int sumOfMinMax(int *arr, int k, int n) {
    // initialize sum as 0
    int sum = 0;
    
    // Traverse all the subarray of size k one by one
    for (int i = 0; i <= (n - k); i++) {
        int min = INT_MAX;
        int max = INT_MIN;
        // traverse the current subarray and find the min and max
        for (int j = i; j < i + k; j++) {
            min = std::min(min, arr[j]);
            max = std::max(max, arr[j]);
        }
        
        // add (min + max) to the sum
        sum += (min + max);
    }
    
    return sum;
}

int main() {
    // Example 1
    int arr1[] = {5, 9, 8, 3, -4, 2, 1, -5};
    int k1 = 4;
    cout<<sumOfMinMax(arr1, k1, sizeof(arr1) / sizeof(arr1[0]))<<endl;

    // Example 2
    int arr2[] = {1, -1, 2, -2, 3, -3};
    int k2 = 2;
    cout<<sumOfMinMax(arr2, k2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
    
    return 0;
}
17
2

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

Сложеност времена = О (н * к)
Сложеност простора = О (1)

Види такође
Примените Стацк и Куеуе користећи Декуе

Овде је временска сложеност полиномна, јер проблем за сваки под-низ решавамо независно. Пошто смо похранили само и и две променљиве за максимум и минимум, потребан простор је константан.

Оптималан приступ

Направите две Декуе д1 и д2, оба декуе-а чувају индексе елемената који могу допринети у минимуму и максимуму под-низа. Декуе д1 садржи елементе у опадајућем редоследу од напред према назад, а д2 садржи елементе у растућем редоследу од напред према назад.

  1. Иницијализујте променљиву суму као 0. Створите два декуе-а д1 и д2. Размотримо први под-низ величине к.
  2. Док је тренутни елемент подниза величине к већи или једнак елементу на задњем делу индекса д1, уклоните задњи елемент Декуе д1.
  3. Док је тренутни елемент подниза величине к мањи или једнак елементу на задњем делу индекса д2, уклоните задњи елемент Декуе д2.
  4. Додајте тренутни индекс на полеђину обе декуре.
  5. Стражњи део деке д1 је индекс максималног елемента подниза, а задњи део декуе д2 је индекс минималног елемента подниза. Додајте променљивој збир збир максималног и минималног елемента.
  6. Пређите преостале под-низове величине к и поновите кораке 2 до 5. За све преостале под-низове користите техника клизних прозора и обрађују само елемент који није присутан у претходном под-низу.
  7. Након преласка свих под-низова, врати суму.

Јава код за проналажење Збир минималних и максималних елемената свих подређаја величине к

import java.util.Deque;
import java.util.LinkedList;

class SumOfMinimumAndMaximumElementsOfAllSubarraysOfSizeK {
    private static int sumOfMinMax(int[] arr, int k) {
        int n = arr.length;
        // initialize sum as 0
        int sum = 0;

        // create 2 deques d1 and d2
        Deque<Integer> d1 = new LinkedList<>();
        Deque<Integer> d2 = new LinkedList<>();

        // first subarray
        for (int i = 0; i < k; i++) {
            // only push the elements that may contribute to maximum
            while (!d1.isEmpty() && arr[d1.peekLast()] <= arr[i])
                d1.removeLast();

            // only push the elements that may contribute to minimum
            while (!d2.isEmpty() && arr[d2.peekLast()] >= arr[i])
                d2.removeLast();

            // add the current elememt's index
            d1.addLast(i);
            d2.addLast(i);
        }

        // sum of min and max for first subarray
        sum += arr[d2.peekFirst()] + arr[d1.peekFirst()];

        // traverse the remaining subarray
        for (int i = k; i < n; i++) {
            // remove the previous element (sliding window technique)
            while (!d2.isEmpty() && d2.peekFirst() <= i - k)
                d2.removeFirst();
            while (!d1.isEmpty() && d1.peekFirst() <= i - k)
                d1.removeFirst();

            // only push the elements that may contribute to maximum
            while (!d1.isEmpty() && arr[d1.peekLast()] <= arr[i])
                d1.removeLast();

            // only push the elements that may contribute to minimum
            while (!d2.isEmpty() && arr[d2.peekLast()] >= arr[i])
                d2.removeLast();

            // add the current element's index
            d1.addLast(i);
            d2.addLast(i);

            // sum of min and max for current subarray
            sum += arr[d2.peekFirst()] + arr[d1.peekFirst()];
        }

        // return total sum
        return sum;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 9, 8, 3, -4, 2, 1, -5};
        int k1 = 4;
        System.out.println(sumOfMinMax(arr1, k1));

        // Example 2
        int arr2[] = new int[]{1, -1, 2, -2, 3, -3};
        int k2 = 2;
        System.out.println(sumOfMinMax(arr2, k2));
    }
}
17
2

Ц ++ код за проналажење Збир минималних и максималних елемената свих подређаја величине к

#include<bits/stdc++.h> 
using namespace std; 

int sumOfMinMax(int *arr, int k, int n) {
    // initialize sum as 0
    int sum = 0;
    
    // create 2 deques d1 and d2
    deque<int> d1;
    deque<int> d2;
    
    // first subarray
    for (int i = 0; i < k; i++) {
        // only push the elements that may contribute to maximum
        while (!d1.empty() && arr[d1.back()] <= arr[i]) {
            d1.pop_back();
        }
        
        // only push the elements that may contribute to minimum
        while (!d2.empty() && arr[d2.back()] >= arr[i]) {
            d2.pop_back();
        }
        
        // add the current element's index
        d1.push_back(i);
        d2.push_back(i);
    }
    
    // sum of min and max for first subarray
    sum += (arr[d2.front()] + arr[d1.front()]);
    
    // traverse the remaining subarray
    for (int i = k; i < n; i++) {
        // remove the previous element (sliding window technique)
        while (!d1.empty() && d1.front() <= (i -k)) {
            d1.pop_front();
        }
        while (!d2.empty() && d2.front() <= (i - k)) {
            d2.pop_front();
        }
        
        // only push the elements that may contribute to maximum
        while (!d1.empty() && arr[d1.back()] <= arr[i]) {
            d1.pop_back();
        }
        
        // only push the elements that may contribute to minimum
        while (!d2.empty() && arr[d2.back()] >= arr[i]) {
            d2.pop_back();
        }
        
        // add the current element's index
        d1.push_back(i);
        d2.push_back(i);
        
        // sum of min and max for current subarray
        sum += (arr[d1.front()] + arr[d2.front()]);
    }
    
    // return total sum
    return sum;
}

int main() {
    // Example 1
    int arr1[] = {5, 9, 8, 3, -4, 2, 1, -5};
    int k1 = 4;
    cout<<sumOfMinMax(arr1, k1, sizeof(arr1) / sizeof(arr1[0]))<<endl;

    // Example 2
    int arr2[] = {1, -1, 2, -2, 3, -3};
    int k2 = 2;
    cout<<sumOfMinMax(arr2, k2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
    
    return 0;
}
17
2

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

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

Види такође
Преокретање реда чекања

Као што смо користили редове који представљају бројеве у опадајућем и растућем редоследу, тако они једном чувају елементе. Стога алгоритам узима линеарно време, а самим тим и потребан простор је такође линеаран.