15,743,541 members
See more:
Coming straight from my last question and my thanks to @Andreas Gieriet I create a program in C that make the following procedure.

Giving a dynamic array with elemnts we want to make a procedure so we can find the lowest sum of the elements in the array.

So if we have that elements: 5 6 1 4 9 3 1 2

the procedure will be the following diagram.

http://prntscr.com/60l705[^]

And in the end we want the minimun of the weight values. In that case 13.

I created the code but i was wondering as the Complexity of the program is O(n^3) if there is any way to reduce it to O(n^2) even in O(N).

C
```#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;
}```

First think using Greedy Algorithm:

C#
```int idx0 = 0;
int idx1 = 1;
int idx2 = N-1;

int sum0 = arr[0];
int sum1 = arr[1];
int sum2 = arr[N - 1];

int max = (sum0 > sum1) ? sum0 : sum1;
max = (sum2 > Max) ? sum2 : Max;

for (i=0; i < N - 1; i++){
sum += arr[i];
}

while ((idx1 + 1) < idx2) {
const int left = (sum0 + arr[idx1]);
const int right = (sum2 + arr[idx2-1]);

if (left <= right && left <= max) {
sum0 = left;
sum1 -= arr[idx1++];
max = (sum1 > sum2) ? sum1 : sum2; //left cannot be greater
} else if (right < left && right <= max) {
sum2 = right;
sum1 -= arr[--idx2];
max = (sum1 > sum2) ? sum1 : sum2; //right cannot be greater
} else break;

//something like return make_pair(idx[1],idx[2]);
//and what I return? I return the value I want? The minimun one?

}```

That is my question, if anyone has any idea post an answer!
Posted
Updated 3-Feb-15 6:26am
v2
Zoltán Zörgő 3-Feb-15 11:26am
1) Are you sure it can be reduced?
2) It seems to be your homework, what about thinking a little bit yourself...?
[no name] 3-Feb-15 11:32am
well not. That was my homework and I solve it. I just though if I can reduce the complexity.
Zoltán Zörgő 3-Feb-15 11:38am
You can eventually...
1) start with the first (i=1) and last (j=N) element for A and C, summarize the rest in B
2) check what would happen if you add [i+1] to A or [j-1] to C - and choose the best direction, by increasing i or decresing j (and updating A, B and C)
3) continue until max(A,B,C) is not decreasing anymore
I am not absolutelly sure this will lead to the result you need, but the algorythm is like M optimization in linear programming
I will try to code it, if I get the time...
[no name] 3-Feb-15 11:44am
what if we use some greedy algorithm? Would be safe?
Zoltán Zörgő 3-Feb-15 11:55am
This is actually one. Safe? It would note eat up your fridge :D

## Solution 1

Here is the code of my approach:
C#
```int max(int A, int B, int C)
{
return Math.Max(A, Math.Max(B,C));
}

void Main()
{
var e = new byte[] {5,6,1,4,9,3,1,2};
var i=0;
var j = e.Length-1;
int A = e[i];
int C = e[j];
int B = 0;
for(int x = i+1 ; x < j; x++) B+=e[x];
var mp = int.MaxValue;
var m = max(A,B,C);
Console.WriteLine("A={0} B={1} C={2}", A, B, C);
while(m < mp)
{
int AL = A+e[i+1];
int CR = C+e[j-1];
int BL = B-e[i+1];
int BR = B-e[j-1];
if(max(AL,BL,C) < max(A,BR,CR) )
{
A=AL;
B=BL;
i++;
}
else
{
C=CR;
B=BR;
j--;
}
mp = m;
m = max(A,B,C);
Console.WriteLine("A={0} B={1} C={2}  MAX={3}", A, B, C, m);
}
Console.WriteLine(mp);
}```

Yes, it is C#, but quite easy to trasscribe it in C/C++, as it is not using any .NET specific. With the sample input you have given, it is terminating in 6 steps:
```A=5 B=24 C=2
A=11 B=18 C=2  MAX=18
A=11 B=17 C=3  MAX=17
A=11 B=14 C=6  MAX=14
A=12 B=13 C=6  MAX=13
A=12 B=4 C=15  MAX=15
13```

Check here: https://dotnetfiddle.net/LC92ZU[^]

Same thing in C :(
C
```#include <stdio.h>
#include <limits.h>
#define max(A,B,C) A > (B > C ? B : C) ? A : (B > C ? B : C)
#define N 10

int main()
{
int e[N] = {1, 1, 8, 1, 1, 3, 4, 9, 5, 2 };
int i=0;
int j = N-1;
int A = e[i];
int C = e[j];
int B = 0;
int x, AL, CR, BL, BR, m, mp = INT_MAX, L, R;
for(x = i+1 ; x < j; x++) B+=e[x];
m = max(A,B,C);
printf("A=%d B=%d C=%d\n", A, B, C);
while(m < mp)
{
AL = A+e[i+1];
CR = C+e[j-1];
BL = B-e[i+1];
BR = B-e[j-1];
L = max(AL,BL,C);
R = max(A,BR,CR);
if(L<R)
{
A=AL;
B=BL;
i++;
}
else
{
C=CR;
B=BR;
j--;
}
mp = m;
m = max(A,B,C);
printf("A=%d B=%d C=%d MAX=%d\n", A, B, C, m);
}
printf("%d", mp);
return 0;
}```

Online: http://ideone.com/v1NFTw[^]

v4
[no name] 3-Feb-15 12:50pm
I knwo some basic things just to understand your code. This will work even with input 1.000.000?
Zoltán Zörgő 3-Feb-15 12:51pm
As long as it fits into memory
[no name] 3-Feb-15 12:54pm
I use that input 1, 1, 8, 1, 1, 3, 4, 9, 5, 2 and I took only the 5 outputs? Why I took wrong output?
[no name] 3-Feb-15 13:34pm
Sir I couldn't manage to solve it. What we make wrong?
Zoltán Zörgő 3-Feb-15 14:30pm
What? With 1, 1, 8, 1, 1, 3, 4, 9, 5, 2
The result is:
A=10 B=9 C=16 MAX=16