**
question–>SPOJ.com - Problem COINS
My program is working for value of n upto 10^7.Earlier i used an array
instead of vector and it was working for n upto 10^8 .I read somewhere that stack cannot
allocate 10^9*4 which is approximately 4gb of memory(which the memory required in my solution as
long int will take 4 bytes.So i went for using vectors.But now also my program
crashes for n above 10^7.What can i do so that my solution works for n upto 10^9.Plz help
**
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
long int max1(long int,vector<long int>&);
int main()
{
long long int n;
int t=10;
vector<long int> sum;
while(t--)
{
cin>>n;
for(long int i=0;i<n;i++)
{
sum.push_back(0);
}
cout<<max1(n,sum)<<"\n";
}
return 0;
}
long int max1(long int n,vector<long int>&sum)
{ if(n==1||n==0){return n;}
if(sum[n]!=0){return sum[n];}
sum[n]=max1(floor(n/2),sum)+max1(floor(n/3),sum)+max1(floor(n/4),sum);
if(sum[n]>n)
{return sum[n];}
else
{
sum[n]=n; return n;
}
}