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
21
-1 2 3 -4 -2 2 1 -3 -2 -3 -4 9 -2 1 7 8 -19 -7 2 4 3
Continuare aici.
