11/23 - Greedy

Se citeşte un şir de n numere întregi. Să se aleagă din şir un număr maxim de elemente astfel încât produsul lor să fie maxim. De exemplu, pentru n = 5 şi şirul 3, –4, 2, –5, –8 se vor alege 3, 2, –5, –8.

#include<iostream>
#include<fstream>
using namespace std;
int n,a[100];
void citire()
{int i;
ifstream f("date");
f>>n;
for(i=0;i<n;i++)
    f>>a[i];
}

void afisare(int x[],int n)
{int i;
for(i=0;i<n;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int main()
{int i,j=0,k=0,p=1,v[100],s=0,b[100],c[100],ok=0,nrneg=0;
citire();
for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
        if(abs(a[i])>abs(a[j]))
            swap(a[i],a[j]);
for(i=0;i<n;i++)
    if(a[i]<0)
        nrneg++;
if(nrneg%2==1)
    for(i=0;i<n;i++)
        if(a[i]<0)
            {a[i]=1;
            break;}
cout<<"Numerele alese"<<endl;
for(i=0;i<n;i++)
    {if(a[i]!=1)
        cout<<a[i]<<" ";
    p*=a[i];}
    cout<<endl<<"Produsul "<<p;
}