#include "stdio.h"
#include "conio.h"
#include "iostream.h"




int suma(int n, int nr[])
{
	int suma=0;
	for(int i=0;i<n;i++)
		suma+=nr[i];
	return suma;
}




int sumaback(int n, int nr[], int x[])
{
	int suma=0;
	for(int i=0;i<n;i++)
	{
		if(x[i]==1)
			suma+=nr[i];
	}
	return suma;
}




bool PotContinua(int n, int nr[], int k, int x[])
{
	if(x[k]<=1)
		return true;
	return false;
}



//backtracking
//pun 0 daca nr nu intra in calculul sumei 
//pun 1 daca intra in suma
//calculez maximul din sumele astea
int backtracking(int n, int nr[], int x[])
{
	int nrsol=0;
	int cont;
	int k;

	static int suma_maxima=suma(n,nr);

	k=0;
	x[k]=-1;
	while(k>=0)
	{
		cont=0;
		while(cont==0 && x[k]<1)
		{
			x[k]++;
			if(PotContinua(n, nr, k, x))
				cont=1;
		}
		if(cont==0)
			k--;
		else
			if(k==n-1)
			{
				if(sumaback(n,nr,x)>suma_maxima)
					suma_maxima=sumaback(n,nr,x);
			}
			else
			{
				k++;
				x[k]=-1;
			}
	}

	return suma_maxima;
}








void main()
{
	int n;
	int nr[20];
	int x[20];

	cout<<"Secventa de suma maxima\n";
	cout<<"Numarul de elemente = ";
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cout<<"nr["<<i<<"]=";
		cin>>nr[i];
	}
	cout<<"Suma maxima="<<backtracking(n,nr,x);
}