Find the mathematic trick behind the program

See more:

C

algorithm

I have created the following program.
It reads an array of numbers and making a process (which shows later in question).

My problem is this. If you test the program on your own, you'll see that in every pass there is a number next to ==>

This number is the minimum of the three in this pass. Following all the possible combinations based on my program we produce those minimum numbers.

But there are numbers which repeately produced. The main question is this:

Is there any way to find how many numbers will be produced more than one time so we can skip many passes droping the complexity of my programm?

Here is the code :

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

#define min(ProfitA,ProfitB,ProfitC) ProfitA > (ProfitB > ProfitC ? ProfitB : ProfitC) ? ProfitA : (ProfitB > ProfitC ? ProfitB : ProfitC)

int sumc(int *array, int start, int end) {
    int sum = 0;
    while (start != end) {
        sum += array[start];
        start++;
    }
    return sum;
}

int main()
{
    int N = 8;
    int array[N] = {8,2,3,6,5,4,8,2}

    int Min = 0;
    int bestA = 0, bestB = 0, bestMin = INT_MAX;
    int A = 0, B = A + 1;
    int i = 0;
    int ProfitA = 0, ProfitB = 0, ProfitC = 0;

    int *pA;
    pA = &array[A];

    int *pB;
    pB = &array[A];

    int *pC;
    pC = &array[ A ];

    ProfitC = sumc(array,B + 1, N );

    for ( A = 0; A < N - 2; ++A){
        ProfitA += *(pA + A) ;

        for ( B = A + 1; B < N - 1; ++B)
        {
             ProfitB += *(pB + B);

         Min = min(ProfitA,ProfitB,ProfitC);

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


            printf( "%2d,%2d or (%3d,%3d,%3d) ", A, B, ProfitA, ProfitB, ProfitC );
            for( i = 0; i < N; ++i )
               printf( "%d%c", array[i], ( ( i == A ) || ( i == B ) ) ? '' : ' ' );
            printf( " ==> %d\n", Min);

            ProfitC -= *(pC  + B + 1 );

        }
        ProfitB = 0;
    ProfitC = sumc(array, A + 3, N  );

    }

    printf("%d\n", bestMin);
}

And here is the ouptut. I care only for the minimum of those maxinum numbers. Sorry for my bad description, but I make the programm that way so you can understand by reading it. For further info make a comment! If you see | represents blocks so we can make the sum.


Output:

0, 1 or (  1,  6, 28) 1|6|10 3 9 6  ==> 28
0, 2 or (  1, 16, 18) 1|6 10|3 9 6  ==> 18
0, 3 or (  1, 19, 15) 1|6 10 3|9 6  ==> 19
0, 4 or (  1, 28,  6) 1|6 10 3 9|6  ==> 28
1, 2 or (  7, 10, 18) 1 6|10|3 9 6  ==> 18
1, 3 or (  7, 13, 15) 1 6|10 3|9 6  ==> 15
1, 4 or (  7, 22,  6) 1 6|10 3 9|6  ==> 22
2, 3 or ( 17,  3, 15) 1 6 10|3|9 6  ==> 17
2, 4 or ( 17, 12,  6) 1 6 10|3 9|6  ==> 17
3, 4 or ( 20,  9,  6) 1 6 10 3|9|6  ==> 20

   The optimal best solution is 15

The alorythm I use to find what we need. I just replaced the Sum function with pointers as we move only one value at the time we add the pointee value to correct sum every time:

N = ...
Salary[0...N-1] = ...
Min = Sum(Salary[0...N-1])
for A=1 to N-2 do loop
  for B=1 to N-1-A do loop
    ProfitA = Sum(Salary[0...A-1])
    ProfitB = Sum(Salary[A...A+B-1])
    ProfitC = Sum(Salary[A+B...N-1])
    ProfitMax = Max(ProfitA, ProfitB, ProfitC)
    if Min is greater than ProfitMax then
      Min = ProfitMax
    end if
  end loop
end loop
Print Min : Permutation