Reading, processing and counting an array setting limits

Question

Last weekend my teacher asked me to create code to solve a problem:

Giving a dynamic array, we want to pass the array elements from a file. The first number in the file N gives us the array length. They follow N numbers, the actual elements of the array.

Three brothers are going to work in the shop of their father for a time. The shop is doing well and every day generates profit which the three brothers may provide. The brothers agreed that they would divide the total time in three successive parts, not necessarily equal duration, and that each one will be working in the shop during one of these parts and collects the corresponding profit on his behalf. But they want to make a deal fairly, so that one received from three more profit someone else. Specifically, they want to minimize the profit the most favored of the three will receive.

Now assume that we have the following array elements:

5 6 1 4 9 3 1 2

The procedure we should make appears in the following diagram:

We want every time to keep the lowest value of weight and in the end to generate a result.

I created the code and it works for all inputs. Is there any way to reduce the complexity from \$\mathcal{O}(n^3)\$ to \$\mathcal{O}(N)\$ if we can keep in mind that this isn't tidied up and probably needs to be.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>


int sum_array(int* array, int cnt)
{
    int res = 0;
    int i;
    for ( i = 0; i < cnt ; ++i)
        res += array[i];
    return res;
}

int main()
{
    FILE* input = fopen("share.in","r");

    int N = 0;
    fscanf(input,"%d",&N);

    int *array = (int*)malloc(N * sizeof(int));

    for (int i = 0; i < N; i++)
        fscanf(input,"%d",&array[i]);

    fclose(input);

    int Min = 0;
    int bestA = 0, bestB = 0, bestMin = INT_MAX;
    int A, B;
    int i;
    for ( A = 0; A < N - 2; ++A)
    {
        for ( B = A + 1; B < N - 1; ++B)
        {
            int ProfitA = sum_array(array, A + 1);
            int ProfitB = sum_array(array + A + 1, B - A );
            int ProfitC = sum_array(array + B + 1, N - 1 - B );

            //here the values are "current" - valid
            Min = (ProfitA > ProfitB) ? ProfitA : ProfitB;
            Min = (ProfitC > Min) ? ProfitC : Min;

            if( Min < bestMin )
                bestA = A, bestB = B, bestMin = Min;

        }
    }
    printf("%d\n", bestMin);
    free(array);
    return 0;
}

Answer 1

Here are some things that may help you improve your code.

Eliminate unused variables

Within main, the variables i, BestA and BestB are declared and some of them set, but they are otherwise unused. They should be omitted from the program.

Don't abuse the comma operator

This line doesn't really need a comma operator:

bestA = A, bestB = B, bestMin = Min;

It should instead be three separate statements, or (if you follow the previous advice) reduced to a single one involving bestMin.

Don't cast the return from malloc

The return value from malloc or calloc is a void * and does not need an explicit cast. See this question for a thorough discussion of the reasons not to, but for me the most compelling reason is that it's simply not needed.

Use const where practical

In your sum_array routine, the values in the array are never altered, which is just as it should be. You should indicate that fact by declaring it like this:

int sum_array(const int* array, int cnt)

Use pointers rather than indexing for speed

Pointers are generally a faster way to access elements than using index variables. Speed may not a particular goal in this program but it's useful to know anyway. For example, your sum_array routine could be written like this:

int sum_array(const int* array, int cnt)
{
    int res;
    for ( res = 0; cnt; --cnt)
        res += *array++;
    return res;
}

Check return values for errors

The calls fopen, fscanf and malloc can each fail. You must check the return values to make sure they haven't or your program may crash (or worse) when given malformed input or due to low system resources. Rigorous error handling is the difference between mostly working versus bug-free software. You should strive for the latter.

Consider separating I/O from the algorithm

The I/O is done first, and then the input values are processed to find the answer. Consider separating those into to separate functions which would both make your program cleaner and also allow for better automated testing (such as automatically generating random values and then checking that the algorithm does the right things).

Reconsider your algorithm

Right now, the sums are recalculated many times, but this isn't strictly necessary. As you iterate through the combinations, the partitioning only moves by one value. So what you could do instead would be to keep the three sums ProfitA, ProfitB and ProfitC and then just add and subtract the particular value that moves from one brother to another.

I've done some reading and it appears to me that the best you can do for complexity is \$\mathcal{O}(N^3)\$ See this question and the many links from it to explain that.

Think about negative numbers

While the problem states that the shop generates profit each day, it doesn't necesarily mean that every time period is profitable. This suggests that some of the time periods could be associated with negative numbers. If we use this input:

8
-5 6 1 4 -9 3 1 2

the program reports a max value of 1, which is correct, but you should verify that it is correct for any possible set of numbers.

Consider adding an "early bailout"

If it ever occurs that ProfitA == ProfitB == ProfitC (as with the values in the previous point) this must be the answer (do you see why?) so the program could exit early with that correct answer.

Eliminate return 0

You don't need to explicitly provide a return 0; at the end of main -- it's created implicitly by the compiler.