[C++, programare dinamică] Subsecvența de sumă maximă – aflarea pozițiilor de început și sfârșit din cei doi vectori, nerecursiv

Aceasta este o continuare la articolul de la acest link. Aici nu se scrie în fișier ci pe ecran.

Vizual

Rezolvare

#include <iostream>
using namespace std;

void subsecv(int A[], int S[], int n, int &st, int &sf)
{
sf = -1;
int max = -(1 << 30); // -infinit
for (int i = 1; i <= n; ++i)
{
if (S[i] > max)
{
max = S[i], sf = i;
}
}

int crt = sf;
while (A[crt] != S[crt])
{
--crt;
}

st = crt;
}

int main()
{
int st, sf;

//int n = 10;
//int A[] = {0, -6, 1, -3, 4, 5, -1, 3, -8, -9, 1};
//int S[] = {0, -6, 1, -2, 4, 9, 8, 11, 3, -6, 1};

//int n = 8;
//int A[] = {0, -2, -3, 4, -1, -2, 1, 5, -3 };
//int S[] = {0, -2, -3, 4, 3, 1, 2, 7, 4 };

int n = 10;
int A[] = { 0, 0, -2, -3, 4, -1, -2, 1, 5, -3, 0 };
int S[] = { 0, 0, -2, -3, 4, 3, 1, 2, 7, 4, 4 };

subsecv(A, S, n, st, sf);

cout << "Inceput: " << st << endl
<< "Sfarsit: " << sf << endl;

return 0;
}

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare /  Schimbă )

Fotografie Google

Comentezi folosind contul tău Google. Dezautentificare /  Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare /  Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare /  Schimbă )

Conectare la %s

%d blogeri au apreciat: