C++ - Secretary Problem using dynamic programming

Overview

About your use of C-arrays: you need to justify this. Sure using them to learn is fine, but here you are not really using them in that way.

In C++ we tend to write algorithms in terms of iterators. This allows us abstract away the actual storage that is used. You can use C-arrays, std::vector or anything else when you use iterators.

You should learn the standard library a bit more. Several of your functions can be replaced with an algorithm from the standard library.

Code Review

Don't use ALL_CAPS for variables. This is (by tradition) reserved for macros. You definitely don't want to clash with macros as they don't follow any scoping rules.

const unsigned int SEED = 42;              // seed for srand()

I would also use constexpr rather than const.

Don't write comments that are explained by the code. The code explains what, comments should explain why.

If you fall into the trap of explaining what in comments the your code will eventually suffer from comment rot. This is where the comments and the code are different (as the comments are not checked by the compiler). Then the engineer that maintains your code will have to work out which is correct. Is it the comments or the code? You don't want that to happen. You want the code to prove it is correct (via tests).

Here in C++ I would have used iterators:

void prime_sequence(unsigned int *data)

// --

template<typename I>
void prime_sequence(I begin, I end)

If you are not sure what iterators are then think of pointers (they don't have to be pointers but that is an easy way to visualize them for a beginner). The begin points at the first element in the container, and the end points one past the end of the container.

So you can loop like this:

 for (I loop = begin; loop != end; ++loop) {
      // Do Stuff
      auto const& val = *loop; // read the value.
      (*loop)         = XXX;   // write the value.
 }

Also this function can be replaced by a one line expression by using std::generate() or std::iota

void prime_sequence(unsigned int *data)
{
    // fill data with values 0 to SEQUENCE_LENGTH-1 in
    for (unsigned int i = 0; i < SEQUENCE_LENGTH; i++)
    {
        data[i] = i;
    }
}

// ----

std::generate(begin, end, [t = 0]() mutable {return t++;}); // requires C++14 or up
// or a better solution suggested by @Rish
std::iota(begin, end, 0);

Same again. But this is replaceable with std::shuffle():

void generate_sequence(unsigned int *data)
{
    // generate random sequence using Fisher–Yates shuffle
    for (unsigned int i = SEQUENCE_LENGTH; i > 0; i--)
    {
        unsigned int position = rand() % i;
        if ((i - 1) != position)
        {
            unsigned int temp = data[i - 1];
            data[i - 1] = data[position];
            data[position] = temp;
        }
    }
}

Here I would use three pairs of iterators:

void simulate(unsigned int *data, unsigned int *max_history, unsigned int *cum_history)


// ---

template<typename ID, typename IM, typename IC>
void simulate(ID beginData, ID endData, 
              IM beginMax,  IM endMax,
              IC beginCum,  IC endCum)

int main()
{

    // OK so you don't want random numbers.
    // Which is fine. But basically this means
    // you get exactly the same results from rand()
    // everytime you run this application.
    srand(SEED);



    // Sure arrays in C.
    // When you talk about arrays in C most people think about
    // dynamically allocated arrays. But these are fine.
    unsigned int data[SEQUENCE_LENGTH] = {0};


    // What I would note is that there is a limit to
    // SEQUENCE_LENGTH before it becomes to large.
    // So in this situation `std::vector` is superior as this
    // limit is much larger.
    // https://stackoverflow.com/a/216731/14065
    unsigned int max_history[SEQUENCE_LENGTH] = {0};





    // Fine:
    prime_sequence(data);
    // using the template version would be:
    prime_sequence(data, data + SEQUENCE_LENGTH);
    // Though I would use:
    prime_sequence(std::begin(data), std::end(data));



    // Don't use `std::endl`.
    // It forces a flush when it is not needed.
    // Simply use `"\n"`.
    std::cout << "max_sum: " << max_sum << " cum_sum: " << cum_sum << std::endl;


    // No point.
    // If your application can only return `0` then
    // not having a value is an indication that your application will
    // never fail.
    return 0;
}