Форум на Исходниках.RU

#define MACROS_ANS(A, B, C, D) \

Sum##D += A; \

if (Sum##D C Ans##D) \

{ \

Ans##D = Sum##D; \

Left##D = Pos##D + 1; \

Right##D = B; \

} \

else if (!(Sum##D C 0)) \

{ \

Sum##D = 0; \

Pos##D = B; \

}

template <typename T>

T GetAnsRing( const T &Array[], int &Left, int &Right )

{

T SumMin = 0;

T AnsMin = 0;

int LeftMin = 0;

int RightMin = 0;

int PosMin = -1;

T SumMax = 0;

T AnsMax = 0;

int LeftMax = 0;

int RightMax = 0;

int PosMax = -1;

T SumArray = 0;

const int Size = ::ArraySize(Array);

for (int i = 0; i < Size; i++)

{

const T Value = Array[i];

SumArray += Value;

MACROS_ANS(Value, i, >, Max)

MACROS_ANS(Value, i, <, Min)

}

AnsMin = SumArray - AnsMin;

const bool Reverse = (AnsMin > AnsMax);

Left = Reverse ? (RightMin + 1) % Size : LeftMax;

Right = Reverse ? (LeftMin + Size - 1) % Size : RightMax;

return(Reverse ? AnsMin : AnsMax);

}

template <typename T>

T CalcInterval( const T &Array[], int &LeftNew, int &RightNew, const uchar &Mask[], int &i, const int &Size )

{

T SumNew = 0;

T AnsNew = 0;

int PosNew = i - 1;

const int End = i;

const int PrevMask = Mask[i];

if (PrevMask)

{

MACROS_ANS(Array[i], i, <, New)

if (++i == Size)

i = 0;

} while ((i != End) && (Mask[i] == PrevMask));

else

{

MACROS_ANS(Array[i], i, >, New)

if (++i == Size)

i = 0;

} while ((i != End) && (Mask[i] == PrevMask));

LeftNew %= Size;

return(PrevMask ? -AnsNew : AnsNew);

}

template <typename T>

T Step( const T &Array[], int &Left, int &Right, const uchar &Mask[], const int From )

{

const int Size = ArraySize(Array);

int LeftNew;

int RightNew;

T Ans = 0;

int Pos = From;

{

const T AnsNew = CalcInterval(Array, LeftNew, RightNew, Mask, Pos, Size);

if (AnsNew > Ans)

{

Left = LeftNew;

Right = RightNew;

Ans = AnsNew;

}

} while (Pos != From);

return(Ans);

}

void IntervalReverse( uchar &Mask[], const int &Left, const int &Right )

{

const uchar Value = (uchar)(1 - Mask[Left]);

if (Left <= Right)

ArrayFill(Mask, Left, Right - Left + 1, Value);

else

{

ArrayFill(Mask, Left, ArraySize(Mask) - Left, Value);

ArrayFill(Mask, 0, Right + 1, Value);

}

template <typename T>

T Solve( const T &Array[], uchar &Mask[], const int Amount = 1 )

{

T Ans = 0;

ArrayResize(Mask, ArraySize(Array));

if (Amount > 0)

{

ArrayInitialize(Mask, 0);

int Left;

int Right;

Ans = GetAnsRing(Array, Left, Right);

IntervalReverse(Mask, Left, Right);

const int From = Left;

T AnsAdd = 0;

for (int i = 1; (i < Amount) && (bool)(AnsAdd = Step(Array, Left, Right, Mask, From)); i++)

{

Ans += AnsAdd;

IntervalReverse(Mask, Left, Right);

}

else

{

ArrayInitialize(Mask, 1);

for (uint i = ArraySize(Array); (bool)i--;)

Ans += Array[i];

}

return(Ans);

}

template <typename T>

void PrintResult( const T &Array[], const uchar &Mask[] )

{

T ArrayOut[];

for (uint i = ArrayCopy(ArrayOut, Array); (bool)i--;)

if (!Mask[i])

ArrayOut[i] = 0;

ArrayPrint(ArrayOut);

}

void OnStart()

{

int Array[] = {1, 2, 3, -5, 1, 2, 3, -10, 1, 1, 2, -20};

uchar Mask[];

for (int i = 0; i < 5; i++)

{

Print("\nIntervals = " + (string)i + ", Sum = " + (string)Solve(Array, Mask, i));

PrintResult(Array, Mask);

}