Збир на сите решенија за под-низи со непарен должина Лек-код


Ниво на тешкотија Лесно
Често прашувано во Скопје
Низа

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

Во овој проблем е дадена низа позитивни цели броеви. Треба да пресметаме и вратиме еден единствен цел број, збир на сите можни под-низи со непарна должина на дадената низа. Под-низа е соседна поделба на низа.

пример

arr = [1,4,2,5,3]
58

објаснување:

Под-низите со непарна должина на arr и нивните збирови се:
[1] = 1, [4] = 4, [2] = 2, [5] = 5, [3] = 3, [1,4,2] = 7, [4,2,5] = 11, [2,5,3] = 10, [1,4,2,5,3] = 15
Додавајќи ги сите овие заедно, добиваме 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

arr = [1,2]
3

објаснување:

Постојат само 2 под-низи со непарна должина, [1] и [2]. Нивната сума е 3.

Пристап (брутална сила)

За да се реши овој проблем со брутална сила, многу е лесно од проблемот да се види дека треба да се обратиме за сите под-парови со непарна должина и да ја пресметаме вкупната сума и да ја вратиме.
Ова можеме да го спроведеме следејќи ги едноставните чекори:

1. Креирај променлива сума за чување на вкупната сума.
2. Извршете ја јамката за сите подпарти со непарна должина почнувајќи од len= 1 и продолжете да ја зголемувате вредноста за 2 додека len <= n (големина на низата).
3. Внатре во оваа јамка, извршете a јамка за почетна позиција на под-низата од i = 0 до i = n-len.
4. Внатре во горната јамка, извршете јамка за оваа под-низа чиј индекс започнува од i и завршува на i +len-1 и додадете ги сите елементи на оваа под-низа.
5. Најпосле вратете го сума.

Имплементација на збирот на сите решенија со непарен должина

Програма C ++

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

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Програма за Java

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

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Анализа на сложеност за збир на сите решенија за непарни должини на лет-код

Временска комплексност

О (n ^ 3): Користевме три јамки во вгнездена форма каде што секоја јамка работи следниве пати:
Првата јамка работи n / 2 пати.
Втората јамка работи (n-len) времиња, каде len е 1,3,4,.
Третата јамка работи len пати.
Вкупното време ќе биде (n / 2) * (n-len)*len. Оттука, горната граница на временската сложеност ќе биде O (n ^ 3) Каде што n е големината на дадената низа.

Комплексноста на просторот 

О (1): Комплексноста на вселената е постојана.

Пристап (оптимизирано време)

Како што можеме да видиме дека над решението за брутална сила има O (n ^ 3) сложеност во времето. Ова можеме да го минимизираме затоа што во горенаведениот пристап го додаваме истиот елемент повеќе пати за различни подгрупи. Ако некако знаеме колку пати се додава одреден елемент или треба да се додаде на вкупната сума, тогаш можеме да ја намалиме временската сложеност од O (n ^ 3) до O (n).

Можеме да анализираме дека ако ги земеме сите под-парови (парна и непарна должина), тогаш во тој случај ќе се појави одреден елемент во индексот i во сите под-низи чиј почетен индекс е помал од еднаков на i, а завршниот индекс е поголем од еднаков на i .

Затоа можеме да кажеме дека вкупниот број на под-низи што содржи arr [i] (0-индексиран) ќе биде еднаков на (i + 1) * (ni).
Нека оваа вредност е x.
Од кои има (x + 1) / 2 под-парови со непарна должина што содржи arr [i].
И под-низи x / 2 дури и должина што содржи arr [i].
Оттука a [i] ќе придонесе (x + 1) / 2 пати во вкупниот збир во нашето решение.

Ова можеме да го видиме со едноставен пример:

Нека arr = [1, 2, 3, 4, 5]

Збир на сите решенија за под-низи со непарен должина Лек-код

Оттука, придонесот на секој елемент arr [i] во непарни под-низи = arr [i] * ((i + 1) * (ni) +1) / 2.
Ова може да се направи со користење на една јамка и оттука, временската сложеност на ова решение ќе биде линеарна.

Имплементација на збирот на сите решенија со непарен должина

Програма C ++

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

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Програма за Java

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

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Анализа на сложеност за збир на сите решенија за непарни должини на лет-код

Временска комплексност

На) : Како што поминавме низ секој елемент од низата само еднаш, па оттука и сложеноста на времето ќе биде O (n). Каде што n е големината на дадената низа.

Комплексноста на просторот 

О (1): Не користевме дополнителна меморија, па оттука и комплексноста во вселената ќе биде постојана.