# PBinfo #1637 – Split – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Fie un şir \( a_1, a_2, …, a_n\) de numere naturale. Se împarte şirul în patru secvenţe astfel încât orice element din şir să aparţină unei singure secvenţe şi fiecare secvenţă să conţină cel puţin două elemente. Mai exact, se identifică trei indici i < j < k astfel încât prima secvenţă este formată din elementele \( a_1, a_2, …, a_i\), a doua din elementele \( a_{i+1}, a_{i+2}, …, a_j\), a treia din elementele \( a_{j+1}, a_{j+2}, …, a_k\) şi ultima din elementele \( a_{k+1}, a_{k+2}, …, a_n\). Pentru fiecare secvenţă se determină costul ei ca fiind diferenţa dintre valoarea maximă şi cea minimă din acea secvenţă.

Cerința
Să se determine o împărţire a şirului în patru secvenţe astfel încât suma costurilor celor patru secvenţe să fie maximă. 

Date de intrare
Fișierul de intrare split.in conţine pe prima linie numărul natural N. Pe linia a doua se găsesc N numere naturale, separate prin câte un spaţiu, reprezentând elementele şirului a.

Date de ieșire
Fișierul de ieșire split.out conţine pe prima linie un singur număr natural reprezentând suma maximă a costurilor celor patru secvenţe. Pe linia a doua se află trei numere naturale i, j şi k, separate prin câte un spaţiu, cu semnificaţia din enunţ.

Restricții și precizări

8 ≤ N ≤ 5.000
0 ≤ \(a_i\) ≤ 100.000.000, pentru orice i = 1...N
O secvenţă poate avea costul 0 (valoarea maximă egală cu valoarea minimă)
Dacă există mai multe soluţii cu aceeaşi sumă maximă, atunci se va alege soluţia cu i minim. Dacă există mai multe soluții cu acelaşi i minim, se alege aceea cu j minim, iar dacă există mai multe soluții cu acelaşi i și j minim, se alege aceea cu k minim.

Exemplu:
split.in

11
9 7 3 0 2 1 8 6 0 11 4
split.out

29
4 7 9
Explicație
Cele 4 secvențe sunt: 9 7 3 0 (cost 9 - 0 = 9)
2 1 8 (cost 8 - 1 = 7)
6 0 (cost 6 - 0 = 6)
11 4 (cost 11 - 4 = 7).
O altă soluţie care obţine tot suma maximă 29 este 5 7 9, dar nu are i minim.

## Cod sursă C++

```cpp
/* 
   Complexitate O (N x N)
*/
#include<fstream>
#define inFile  "split.in"
#define outFile "split.out"
#define Dim 10005
using namespace std;
int a[Dim], minst[Dim], mindr[Dim], maxdr[Dim], maxst[Dim], n;
int main()
{
	int i, j, k, x, di, dk, maxim, minim, xi, xj, xk;
	int solst, soldr, solmax;
	// citire
	ifstream fin(inFile);
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> a[i];
	fin.close();
	//min max stg
	minst[1] = maxst[1] = a[1];
	for (i = 2; i <= n; i++)
	{
		if (a[i] > maxst[i-1]) maxst[i] = a[i];
		else maxst[i] = maxst[i-1];
		if (a[i] < minst[i-1]) minst[i] = a[i];
		else minst[i] = minst[i-1];
	}
	//min max drp
	mindr[n] = maxdr[n] = a[n];
	for (i = n - 1; i >= 1; i--)
	{
		if (a[i] > maxdr[i+1]) maxdr[i] = a[i];
		else maxdr[i] = maxdr[i+1];
		if (a[i] < mindr[i+1]) mindr[i] = a[i];
		else mindr[i] = mindr[i+1];
	}
	// calcul
	solmax = 0;
	di = dk = 0;
	xi = 2; xj = 4; xk = 6;
	for (j = 4; j <= n - 3; j++)
	{
		// maximul din stanga: i=2..j-2
		if (a[j] > a[j - 1])
		{
			maxim = a[j];
			minim = a[j - 1];
		}
		else
		{
			maxim = a[j - 1];
			minim = a[j];
		}
		solst = maxim - minim + maxst[j-2] - minst[j-2];
		di = j - 2;
		for (i = j - 2; i > 2; i--)
		{
			if (a[i] > maxim) maxim = a[i];
			if (a[i] < minim) minim = a[i];
			x = maxim - minim + maxst[i-1] - minst[i-1];
			if (solst <= x) { solst = x; di = i-1;}
		}
		//maximul din dreapta k=j+2..n-2
		if (a[j+1] > a[j+2])
		{
			maxim = a[j+1];
			minim = a[j+2];
		}
		else
		{
			maxim = a[j+2];
			minim = a[j+1];
		}
		soldr = maxim - minim + maxdr[j+3] - mindr[j+3];
		dk = j + 2;
		for (k = j + 3; k <= n - 2; k++)
		{
			if (a[k] > maxim) maxim = a[k];
			if (a[k] < minim) minim = a[k];
			x = maxim - minim + maxdr[k+1] - mindr[k+1];
			if (soldr < x) { soldr = x; dk = k;}
		}
		x = solst + soldr;
		if (x > solmax) 
		{
			solmax = x;
			xi = di; 
			xj = j;
			xk = dk;
		}
	}
	ofstream fout(outFile);
	fout << solmax << "\n";
	fout << xi << " " << xj << " " << xk << "\n";
	fout.close();
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1637)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1637/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1637/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)