Директно решење грубом силом подразумевало би да се провере сви сегменти узастопних елемената, да се за сваки израчуна збир и да се провери да ли је тај збир једнак траженом. Сви сегменти се могу набројати угнежђеним петљама, где спољна петља пролази кроз леве крајеве сегмента (\(i\) узима вредности од \(0\) па до \(n-1\)), а унутрашња петља пролази кроз десне крајеве сегмената (од вредности \(i\) па до \(n-1\)). Збир можемо рачунати алгоритмом сабирања или применом библиотечких функција.
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int brojSegmenataDatogZbira(const vector<int>& a, int trazeniZbir) {
// broj elemenata niza
int n = a.size();
// broj segmenata trazenog zbira
int broj = 0;
// prolazimo sve segmente
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// izracunavamo zbir segmenta [i, j]
int zbir = 0;
for (int k = i; k <= j; k++)
zbir += a[k];
// proveravamo da li je zbir tog segmenta jednak trazenom
if (zbir == trazeniZbir)
broj++;
}
}
return broj;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
// ucitavamo trazeni zbir
int trazeniZbir;
cin >> trazeniZbir;
// ucitavamo niz
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// brojimo segmente datog zbira
cout << brojSegmenataDatogZbira(a, trazeniZbir) << endl;
return 0;
}Сложеност. Сложеност овог приступа је кубна у односу на димензију \(n\) тј. \(O(n^3)\). Наиме, постоји квадратни број сегмената и за сабирање елемената сваког од њих потребно је линеарно време.
Претходна процена је извршена прилично грубо, јер иако је сложеност сабирања сегмента линеарна, нису сви сегменти дужине \(n\), међутим, и прецизнија анализа ће довести до истог резултата. Унутрашња петља се извршава \(j-i+1\) пута (толико пута се врши операција сабирања), што одговара дужини сегмента. Спољне петље које набрајају све сегменте набрајају један сегмент дужине \(n\), два сегмента дужине \(n-1\), три сегмента дужине \(n-2\), … и \(n\) сегмената дужине 1. Значи да је број корака једнак \(1 \cdot n + 2\cdot(n-1) + 3\cdot (n-2) + \ldots + (n-1) \cdot 2 + n \cdot 1\). Дакле, сегмената дужине \(k\) има \(n-k+1\), па важи да је претходни збир једнак
\[\sum_{k=1}^n k(n-k+1) = (n+1)\cdot \sum_{k=1}^n k - \sum_{k=1}^n{k^2} = (n+1) \cdot \frac{n(n+1)}{2} - \frac{n(n+1)(2n+1)}{6}\]
Ово је реда величине \(\frac{n^3}{2} - \frac{2n^3}{6} = \frac{n^3}{6}\), што је \(O(n^3)\).
Алгоритам грубе силе који посебно рачуна збир сваког сегмента се може унапредити ако се збирови рачунају инкрементално тј. ако се искористи чињеница да се збир сваког сегмента који се добија проширивањем претходног сегмента једним елементом може лако израчунати на основу збира претходног сегмента, тако што се збир претходног сегмента увећа за текући елемент низа. Ту идеју смо видели, на пример, у задатку Највећи збир префикса.
Дакле, опет можемо набрајати све сегменте угнежђеним петљама, на почетку тела спољашње петље збир иницијализујемо на нулу, у унутрашњој петљи збир увећавамо за елемент \(a_j\) и, ако је он једнак траженом, исписујемо индексе интервала \([i, j]\).
#include <iostream>
#include <vector>
using namespace std;
int brojSegmenataDatogZbira(const vector<int>& a, int trazeniZbir) {
// broj elemenata niza
int n = a.size();
// broj segmenata trazenog zbira
int broj = 0;
// prolazimo sve segmente
for (int i = 0; i < n; i++) {
// zbir segmenta [i, j]
int zbir = 0;
for (int j = i; j < n; j++) {
// izracunavamo zbir segmenta [i, j] na osnovu zbira segmenta [i, j-1]
zbir += a[j];
// proveravamo da li je zbir tog segmenta jednak trazenom
if (zbir == trazeniZbir)
broj++;
}
}
return broj;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
// ucitavamo trazeni zbir
int trazeniZbir;
cin >> trazeniZbir;
// ucitavamo niz
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// brojimo segmente datog zbira
cout << brojSegmenataDatogZbira(a, trazeniZbir) << endl;
return 0;
}Сложеност. Овим је избегнута линеарна сложеност за израчунавање збира тренутног интервала тј. да се збир сваког наредног интервала добија у константном времену, тако да је сложеност целог алгоритма редукована на квадратну тј. \(O(n^2)\).
Опет би се прецизнијом анализом добио исти резултат. Наиме, сви збирови сегмената који почињу на позицији \(0\) рачунају се помоћу \(n\) сабирања, збирови сегмената који почињу на позицији \(1\) рачунају се помоћу \(n-1\) сабирања итд. Укупан број сабирања је, дакле, \(1+\ldots+n = \frac{n(n+1)}{2}\), што је \(O(n^2)\).
Задатак се, може решити и доста ефикасније од овога.