Question

Se da un sir de numere intregi. Se cere sa se determine subsecventa de suma maxima
pozitiva pentru acest sir, prin 2 metode, una de complexitate O(n), alta de
complexitate O(n log(n)).

Answer 1

Salut!

1. Complexitate O(n)

#include <iostream>

#include <climits>

using namespace std;

const int N = 100001;

int main() {

   int n, v[N], sMax = INT_MIN, s = 0;

   cin >> n;

   for (int i = 1; i <= n; ++i) {

       cin >> v[i];

       //daca suma noastra e negativa

       if (s < 0) {

           //resetam suma la 0

           s = 0;

       }

       s += v[i];

       //calculam sMax

       if (s > sMax) {

           sMax = s;

       }

   }

   cout << sMax;

   return 0;

}

Explicatie

Totul se intampla intr-un singur for de la 1 la n, de aici rezultand complexitatea O(n)

2. Complexitate O(n log(n))

#include <iostream>

#include <climits>

using namespace std;

const int N = 100001;

int sumaMaxima(int v[], int st, int dr) {

   //daca n <= 1

   if (dr <= st) {

       return v[st];

   }

  //mijlocul tabloului

   int m = (st + dr) / 2;

   //gasim subsecventa de suma maxima a partii din st cu tot cu elementul din mijloc

   int stMax = INT_MIN;

   int s = 0; //initializam suma cu 0

   for (int i = m; i >= st; i--) {

       s += v[i];

       if (s > stMax) {

           stMax = s;

       }

   }

   //gasim subsecventa de suma maxima a partii din st fara elementul din mijloc

   int drMax = INT_MIN;

   s = 0; //resetam suma

   for (int i = m + 1; i <= dr; i++) {

       s += v[i];

       if (s > drMax) {

           drMax = s;

       }

   }

   //gasim recursiv subsecventa de suma maxima pentru partea din stanga si dreapta, apoi luam maximul celor 2

   int stDrMax = max(sumaMaxima(v, st, m), sumaMaxima(v, m + 1, dr));

   //returnam maximul dintre ce am calculat mai devreme si suma maxima din st + suma maxima din dr

   return max(stDrMax, stMax + drMax);

}

int main() {

   int n, v[N];

   cin >> n;

   for (int i = 1; i <= n; ++i) {

       cin >> v[i];

   }

   cout << sumaMaxima(v, 1, n);

   return 0;

}

Explicatie

• Folosim Divide et Impera pentru a gasi suma maxima din partea din stanga a tabloului si a celei din dreapta

Cum functioneaza Divide et Impera in cazul nostru

• Ne impartim tabloul in 2 parti egale (semi-egale dupa caz)
• Calculam recursiv subsecventa de suma maxima din stanga
• Calculam recursiv subsecventa de suma maxima din dreapta
• Gasim subsecventa de suma maxima care trece prin mijloc, iar rezultatul nostru va fi maximul celor 3

De ce complexitatea este O(n log(n))

• Facem 2 apeluri recursive ambele cu inputul n/2 (jumatatea stanga si jumatatea dreapta). Ca sa gasim subsecventa de suma maxima care trece prin mijloc vom avea O(n) in cel mai rau caz.