[C++, programare dinamică] Problema subsecvenței de produs maxim

Problema este de la finalul acestui fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Enunțul problemei

b) Se cere o subsecvență de produs maxim, iar numerele sunt reale. Rezolvați problema atât pentru numere strict pozitive cât și pentru numere nenule (dar care pot fi negative).

Rezolvarea completă

Este aici. Mai jos sunt rezolvări care funcționează doar pe anumite date de intrare.

Cod sursă 1

In această secțiune se rezolvă problema pentru cazul numerelor reale strict pozitive, rezolvarea fiind foarte asemănătoare cu problema subsecvenței de sumă maximă.

Rezolvarea care folosește programarea dinamică este funcția subsecv6.

#include <fstream>
#include <iostream>
using namespace std;

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

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

 for (int st = 1; st <= N; ++st)
 {
  for (int dr = st; dr <= N; ++dr)
  {
   float temp = 1;
   for (int i = st; i <= dr; ++i)
    temp *= A[i];

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

 return max;
}


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

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

 return max;
}

float subsecv6(float A[], int N,
 int &inceput, int &sfarsit)
{
 float max = A[1];
 int inceput_temp = 1;
 float 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()
{
 float 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.
 float max = subsecv6(A, N,
  inceput, sfarsit);
 out << max << " " << inceput <<
  " " << sfarsit << endl;
 out.close();

 return 0;
}

Cod sursă 2

In această secțiune se rezolvă problema pentru cazul numerelor întregi (negative, zero și pozitive).

#include <fstream>
#include <vector>
using namespace std;

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

double produs(vector<double> &A, int a, int b)
{
    double r = A[a];
    for (int i = a + 1; i <= b; ++i)
    {
        r *= A[i];
    }
    return r;
}

double produs_maxim_secv_fara_0(vector<double> &A, int a, int b,
    int &inceput, int &sfarsit)
{
    if (a == b)
    {
        inceput = a;
        sfarsit = a;
        return A[a];
    }

    int primul_negativ = -1;
    int negative = 0;
    int ultimul_negativ;

    for (int i = a; i <= b; ++i)
    {
        if (A[i] >= 0)
        {
            continue;
        }

        ++negative;
        if (primul_negativ < 0)
        {
            primul_negativ = i;
        }
        ultimul_negativ = i;
    }

    if (negative % 2 == 0)
    {
        inceput = a;
        sfarsit = b;
        return produs(A, a, b);
    }

    if (primul_negativ + 1 > b)
    {
        inceput = a;
        sfarsit = b - 1;
        return produs(A, a, b - 1);
    }

    if (ultimul_negativ - 1 < a)
    {
        inceput = a + 1;
        sfarsit = b;
        return produs(A, a + 1, b);
    }

    double p1 = produs(A, primul_negativ + 1, b);
    double p2 = produs(A, a, ultimul_negativ - 1);
    if (p1 > p2)
    {
        inceput = primul_negativ + 1;
        sfarsit = b;
        return p1;
    }

    inceput = a;
    sfarsit = ultimul_negativ - 1;
    return p2;
}

double subsecv(vector<double> &A, int N,
    int &inceput, int &sfarsit)
{
    double maxim = A[1];
    int i = 1, j;
    while (i <= N)
    {
        while (i <= N && A[i] == 0)
        {
            ++i;
        }
        j = i;
        while (j <= N && A[j] != 0)
        {
            ++j;
        }

        int inceput_temp, sfarsit_temp;
        double p_nou = produs_maxim_secv_fara_0(A, i, j - 1,
            inceput_temp, sfarsit_temp);
        if (maxim <= p_nou)
        {
            maxim = p_nou;
            inceput = inceput_temp;
            sfarsit = sfarsit_temp;
        }

        i = j;
    }

    return maxim;
}

Intrări și ieșiri

1. (pentru primul cod sursă)

6
2 3 4 2 3 1

rezultă ieșirea:

144 1 5

2. (pentru primul cod sursă)

5
2 2 0.1 2 2

rezultă ieșirea:

4 1 2

Alte intrări

4

3 5 1 2

10

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

6

-2 -3 -4 -2 -3 1

5

2 5 -1 -2 -4

9

1 2 0 -4 5 6 0 7 1

2

3 -8

2

-8 3

1

-3