K ұзындығының максималды орташа қосындысын табыңыз


Күрделілік дәрежесі оңай
Жиі кіреді Amazon
Array

Проблемалық мәлімдеме

Сізге ан массив бүтін сандар мен k саны. Есептер k ұзындығының максималды орташа қосындысын табуды сұрайды. Ішкі массив - бұл бастапқы массив элементтерінің іргелес блогынан құрылған массивтен басқа ештеңе емес

мысал

arr[] = {1,3,12,34,76,10}
[2, 4]

Түсініктеме: 2 индексінен 4 индексіне дейінгі массив орташа максимумға ие. Сонымен [2,4] - ұзындықтың орташа максималды орташа мәні 2.

arr[] = {1,-2,8,3,-6,9}
[1, 3]

Түсініктеме: 1 индексінен 3 индексіне дейінгі массив орташа максималды мәнге ие.

 

K ұзындығының максималды орташа қосындысын табу алгоритмі

1. Declare a currentSum.
2. Set the currentSum to arr[0].
3. Traverse the array from i=1 to less than the length of n.
  Store and update the addition of currentSum and arr[i] into the currentSum.
4. Set maximumSum to currentSum.
5. Set END to k-1.
6. Traverse the array from i=k to k to i < n.
7. Set sum to sum + arr[i] - arr[i - k].
  Check if the sum is greater than maximumSum.
    1. Set sum to maximumSum.
    2. Set END to i.
8. Return END – k + 1.

 

Түсіндіру

Бізге бүтін сандар жиыны және k саны беріледі. K өлшемді ішкі жиымның максималды орташа мәнін білуіміз керек. Бұл дегеніміз, біз табатын орташа мән массивтің k іргелес сандарынан болуы керек. Сонымен, біз ішкі жиым ішіндегі k сандарының орташа мәнін табамыз. Егер біз шартты жарияладық k қарағанда үлкен n,. Егер ол шын болса, -1 мәнін қайтарыңыз. Демек, егер k мәні n-ден үлкен болса, демек, егер бізде k мәні жарамсыз болса, онда k жиымның өлшемінен үлкен болуы мүмкін емес.

Біз қазірдің өзінде жасадық ағымдағы сома. Берілген жиымның бірінші мәнін currentSum-ге көшіріңіз. Содан кейін біз 1 индексінен массивті айналып өтетін боламыз, өйткені біз қазірдің өзінде currentSum мәні бойынша амал жасағанбыз. Сонымен, біз массивті айналып өтіп, currentSum және arr [i] алдыңғы элементінің қосындысын алып, currentSum-ға сақтаймыз.

Біз мәнін орнаттық максимум ағымдық қосындының (k-1) позициясына дейін және k-1 дейін END. Массивті k-ші позициядан массивтің соңғы элементіне дейін өтіңіз. Біз айырмашылықты аламыз arr [i] және arr [i - k] және біз оны қосындының мәніне қосамыз және оны қосындыға дейін сақтаймыз, сонымен қатар k позициясынан бастаған теріс мәнімізге алаңдамауымыз керек, сондықтан ол жерде ешқандай айырмашылық болмайды. Егер қосынды максимум қосындысынан үлкен болса, максимум қосындыны қосындының мәні мен ақырғы мәнінен i-ге орнатыңыз. Біз массивтің ұзындығына жеткенше сол процесті қайталаймыз. Содан кейін біз қайтып ораламыз END - k + 1.

Бұл әдіс жылжымалы терезе техникасы деп те аталады.

K ұзындығының максималды орташа қосындысын табыңыз

 

K ұзындығының максималды орташа қосындысын табуға арналған код

C ++ коды

#include<iostream>
using namespace std;
int getMaxAvgSubArray(int arr[], int n, int k)
{
    if (k > n)
        return -1;
    int currentSum;
    currentSum = arr[0];
    for (int i = 1; i < n; i++)
        currentSum = currentSum + arr[i];
    int maximumSum = currentSum;
    int END = k - 1;
    for (int i = k; i < n; i++)
    {
        currentSum = currentSum + arr[i] - arr[i-k];
        if (currentSum > maximumSum)
        {
            maximumSum = currentSum;
            END = i;
        }
    }
    return END - k + 1;
}
int main()
{
    int arr[] = {1,3,12,34,76,10};
    int k = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    int start=getMaxAvgSubArray(arr, n, k);
    cout<<"Maximum average subarray: ["<< start<<" "<< (start + k - 1)<<"]";
    return 0;
}
Maximum average subarray: [2 4]

Java коды

class MaximumAverageSubarray
{
    public static int getMaxAvgSubArray(int []arr,int n, int k)
    {
        if (k > n)
            return -1;

        int currentSum = arr[0];

        for (int i = 1; i < k; i++)
            currentSum = currentSum + arr[i];

        int maximumSum = currentSum;
        int END = k - 1;

        for (int i = k; i < n; i++)
        {
            currentSum = currentSum + arr[i] - arr[i-k];

            if (currentSum > maximumSum)
            {
                maximumSum = currentSum;
                END = i;
            }
        }
        return END - k + 1;
    }
    public static void main (String[] args)
    {
        int []arr = {1,3,12,34,76,10};
        int k = 3;
        int n = arr.length;
        int start=getMaxAvgSubArray(arr, n, k);
        System.out.println("Maximum average subarray: ["+start+" "+ (start + k - 1)+"]");
    }
}
Maximum average subarray: [2 4]

Күрделілікті талдау

K ұзындығының максималды орташа қосындысын табуға уақыттың күрделілігі

Біз массив арқылы бір рет өткендіктен, уақыттың сызықтық күрделілігі бар. O (N) қайда «N» - бұл массивтегі элементтер саны.

K ұзындығының максималды орташа қосындысын табуға арналған кеңістіктің күрделілігі

Біз кірісті сақтауға арналған массивті қолданғандықтан, бізде сызықтық кеңістіктің күрделілігі бар. O (N) қайда «N» - бұл массивтегі элементтер саны.