[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.