[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;
}