[C++, programare dinamică] Subsecvența de sumă maximă – problema (a) – suma și pozițiile de început și sfârșit

Enunțul subproblemei:

a) Modificați implementările date pentru a afișa și pozițiile de început și de sfârșit a unei subsecvențe de sumă maximă.

Problemă extrasă din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Fișier intrare

10
-6 1 -3 4 5 -1 3 -8 -9 1

Fișier ieșire

11 4 7

Codul sursă

#include <fstream>
using namespace std;

const int inf = 1 << 30;
const int maxn = 2001;

int subsecv4(int A[], int N,
int &inceput, int &sfarsit)
{
int max = -inf;

for (int st = 1; st < N; ++st)
{
for (int dr = st; dr <= N; ++dr)
{

int temp = 0;
for (int i = st; i <= dr; ++i)
temp += A[i];

if (temp > max)
{
inceput = st;
sfarsit = dr;
max = temp;
}
}
}

return max;
}


int subsecv5(int A[], int N,
int &inceput, int &sfarsit)
{
int max = -inf;

for (int st = 1; st < N; ++st)
{
int temp = 0;
for (int dr = st; dr <= N; ++dr)
{
temp += A[dr];
if (temp > max)
{
inceput = st;
sfarsit = dr;
max = temp;
}
}
}

return max;
}

int subsecv6(int A[], int N,
int &inceput, int &sfarsit)
{
int max = A[1];
int inceput_temp = 1;
int S[maxn];
S[1] = A[1];
inceput = sfarsit = 1;

for (int i = 2; i <= N; ++i)
{
if (S[i - 1] + A[i] > A[i])
{
S[i] = S[i - 1] + A[i];
}
else
{
inceput_temp = i;
S[i] = A[i];
}

if (S[i] > max)
{
inceput = inceput_temp;
sfarsit = i;
max = S[i];
}
}

return max;
}

int main()
{
int A[maxn], N;

ifstream in("subsecv.in");
in >> N;
for (int i = 1; i <= N; ++i)
{
in >> A[i];
}
in.close();

ofstream out("subsecv.out");
int inceput, sfarsit;
// Toate cele 3 functii de mai sus se
// apeleaza identic.
int max = subsecv4(A, N,
inceput, sfarsit);
out << max << " " << inceput <<
" " << sfarsit << endl;
out.close();

return 0;
}

Adăugiri

Pe infoarena.ro am găsit o soluție de complexitate O(N) care, modificată puțin, dă și pozițiile de început și de sfărșit:

int subsecv_infoarena(int A[], int N,
int &inceput, int &sfarsit)
{
int sum[maxn], best[maxn];
sum[0] = 0;
for (int i = 1; i <= N; ++i)
{
sum[i] = A[i] + sum[i - 1];
}

int inceput_temp = 1;

int min = sum[0];
int bestSum = -inf;
for (int i = 1; i <= N; ++i)
{
best[i] = sum[i] - min;
if (min > sum[i])
{
min = sum[i];
inceput_temp = i + 1;
}
if (bestSum < best[i])
{
bestSum = best[i];
inceput = inceput_temp;
sfarsit = i;
}
}

return bestSum;
}

Alte date de intrare

12
99 -99 -6 1 -3 4 5 -1 3 -8 -9 1

și via infoarena.ro:

21

-1 2 3 -4 -2 2 1 -3 -2 -3 -4 9 -2 1 7 8 -19 -7 2 4 3

Continuare aici.

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: