new program

[ReputGlory1]

I made the program.

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
    ofstream fout;
    ifstream fin;
    fin.open("share.in");
    fout.open("share.out");

    int n;
    fin >> n;
    vector<int> array1(n);

    for(int i=0; i<n; i++)
    {
        fin >> array1[i];
    }

    int suma=0, sumb=0, sumc=0, a=1, b=1, c=n-2, a1=0, b1=0, c1=0, mikroterosum=10000000;

        while(c>0)
        {
                while(a1<a)
                {
                suma+=array1[a1];
                a1++;
                }
                while(b1<b)
                {
                sumb+=array1[(a1+b1)];
                b1++;
                }
                while(c1<c)
                {
                sumc+=array1[(a1+b1+c1)];
                c1++;
                }


        if(max(suma,max(sumb,sumc))<=mikroterosum)
            {
                mikroterosum=min(mikroterosum, max(suma,max(sumb,sumc)));
            }



                suma=0;
                sumb=0;
                sumc=0;

                a1=0;
                b1=0;
                c1=0;

                c--;
                b++;


    if(c==0)
        {
            ++a;
            b=1;
            c=n-a-1;
        }
            }


    fout<<mikroterosum;


    fin.close();
    fout.close();

    return 0;
}

It works but it takes a lot time because it's N^3(3 whiles)

Can i make it faster?


I want to find the min of all max sums that i can have

f.e if the nums are 8 5 6 1 4 9 3 1 2

The best solution is 13
5+6+1=12, 4+9=13, 3+1+2=6.

Can i make it like this?

int n;
    cin >> n;
    int array1[n];
    int array2[n];
    array2[0]=array1[0];

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

   for(int i=1; i<n; i++)
    {
        array2[i]=array1[i-1]+array1[i];
    }

    int a=n/3, b=2*(n/3);
    int suma=array2[a-1], sumb=array2[b-1]-suma, sumc=array2[n-1]-sumb-suma;
    int maxnum=max(suma, max(sumb, sumc));



    if(max((array2[a-i],(sumb+array1[a-i]))<maxnum))
    {
        a--;
        int suma=array2[a-i], sumb=array2[b-i]-suma, sumc=array2[n-1]-sumb-suma;
    }
    if(max((array2[a-],(sumb+array1[a-i]))<maxnum))
    {
        a--;
        int suma=array2[a-i], sumb=array2[b-i]-suma, sumc=array2[n-1]-sumb-suma;
    }
    if(max((array2[a-i],(sumb+array1[a-i]))<maxnum))
    {
        a--;
        int suma=array2[a-i], sumb=array2[b-i]-suma, sumc=array2[n-1]-sumb-suma;
    }
    if(max((array2[a-i],(sumb+array1[a-i]))<maxnum))
    {
        a--;
        int suma=array2[a-i], sumb=array2[b-i]-suma, sumc=array2[n-1]-sumb-suma;
    }

It doesnt work but in this way

[keskiverto]

In your latter program: Lines 4 and 5. Variable length arrays are not supported in C++ standard. Your first program does use std::vector and so should this.



The sum over all input (sumT) is constant. You can calculate sumC = (sumT - sumA - sumB);


Optimal solution has sumA == sumB == sumC == sumT/3. That is not possible for all inputs.
=> If any subsum is clearly below the sumT/3, then the other(s) must be over sumT/3.