3
\$\begingroup\$

I have created a program where I first set the size of the array and how many times I will look for consecutive values, then I fill in the array and finally I insert the consecutive values, it should look for the least consecutive value it finds in the array.

consecutive value means the sum of the elements in the array consecutively.

example:

7 4 // Array size and consecutive values
6 4 2 7 10 5 1 // arrangement
1 3 4 2 // Consecutive values

Answer = 1,12,19,6

Explanation

The lowest element of the array is the one in the last position which is 1, the answer is equal to 1.

the lowest segment is the one furthest to the left 6 4 2, the sum of which equals 12.

the answer is obtained by choosing segment 6 4 2 7, which equals 19.

there are two segments with a minimum cost equal to 6, segments 4 2 and 5 1.

How can it be improved?

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

void suma_elementos(int elemento);
vector<int>elementos, consecutivos;
int n, q, consecutivo, total, final = 99999999;

int main()
{
    cin >> n >> q;
    elementos.resize(n);
    consecutivos.resize(q);

    for (int i = 0; i < n; i++)
    {
        cin >> elementos[i];
    }
    for (int i = 0; i < q; i++)
    {
        cin >> consecutivos[i];
    }

    for (int i = 0; i < q; i++)
    {
        suma_elementos(consecutivos[i]);

        for (int j = 0; j < consecutivo; j++)
        {
            for (int c = 0; c < consecutivos[i]; c++)
            {
                total += elementos[c + j];
            }

            if (total < final)
            {
                final = total;
            }
            total = 0;
        }
        cout << final << " ";
        //reset
        consecutivo = 0;
        final = 99999999;
        total = 0;
    }

    return 0;
}

//Suma de elementos
void suma_elementos(int elemento)
{

    int proporcion = n;

    while (proporcion >= elemento)
    {
        proporcion--;
        consecutivo++;
    }
}

edit 1:The program in small arrangements works well, but in large ones it's very slow

edit 2:must not have negative numbers in the sequence

\$\endgroup\$
  • 2
    \$\begingroup\$ Since you want to optimise it, can you provide a file with the input values which can give measurable and consistent timings in the profiler ? Also to save the manual typing, and the delay introduced because of that, please add the code that reads from a file. Right now, cin >> valor; recorrido.push_back(valor); this block cannot be profiled correctly, since time taken by a human to enter a number is far more than the time a push_back takes. \$\endgroup\$ – aki Jul 5 at 17:20
  • 2
    \$\begingroup\$ If this is a programming challenge, can you please add the programming-challenge flag and add a link to the challenge. Nice question otherwise. \$\endgroup\$ – pacmaninbw Jul 5 at 18:58
  • 1
    \$\begingroup\$ Please post a samlpe, or two, input that shows that the program is slow. \$\endgroup\$ – R Sahu Jul 5 at 21:42
  • 1
    \$\begingroup\$ Also, is it possible to have negative numbers in the sequence? \$\endgroup\$ – R Sahu Jul 5 at 21:49
  • 1
    \$\begingroup\$ @akki That is not quite correct, as the contents of a file can be piped in to stdin. Reading from stdin with cin is a better choice, as you can profile with many different input files without recompiling, whereas reading from a hardcoded file makes testing and profiling much more cumbersome. \$\endgroup\$ – spyr03 Jul 5 at 22:49
4
\$\begingroup\$
  • Avoid globals. consecutivo is particularly confusing. It is too easy to miss the fact that it is reset to 0 at each iteration. Always prefer returning a value:

    int suma_elementos(int elemento)
    {
        int proporcion = n;
        int consecutivo = 0;
        while (proporcion >= elemento)
        {
            proporcion--;
            consecutivo++;
        }
        return consecutivo;
    }
    

    and use it in your loop as

        int consecutivo = suma_elementos(consecutivos[i]);
    
  • Now it is obvious that suma_elementos does not really need to loop. You have an invariant proporcion + consecutivo == n. At the end of the last iteration you also have proporcion == elemento, which means that consecutivo = n - elemento. In other words,

    int suma_elementos(int elemento)
    {
        return n - elemento;
    }
    
  • Now I would rather not bother to have suma_elementos at all (besides, with my poor Spanish I have an impression that the name is rather misleading). The loop would become

        for (int j = 0; j < n - consecutivos[i]; j++)
    

    Honestly, it is much easier to understand.

  • final = 99999999; is very fragile. Consider a ramp-up loop:

      final = 0;
      for (int j = 0; j < consecutivos[i]; j++) {
          total += elementos[j];
      }
    
  • Your code complexity is \$O(n*k)\$ (k being a width of the window). Notice that after the ramp-up you don't need to recompute the sums of k elements: as the window shifts, one element enters, another leaves:

      final = total;
      for (int leave = 0, enter = base[i]; enter < n; leave++, enter++) {
          total += elementos[enter] - elementos[leave];
          if (total < final) {
              final = total;
          }
      }
    

    obtaining \$O(n + k)\$ complexity.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.