Array/vector of size 10^9 problem


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


using namespace std;
long int max1(long int,vector<long int>&);
int main()
long long int n;
int t=10;
vector<long int> sum;
for(long int i=0;i<n;i++)
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];}
{return sum[n];}
 sum[n]=n; return n;

The memory limits for the SPOJ judge permit array (or vector )length only upto 10^7. There is no option but to reduce memory usage.

Hint : Use an array upto 10^7 and for larger values , determine how you can use these values to optimize. Something like DP

i used vector only to memoize the values which are calculated earlier to reduce the time limit because earlier i got time limit exceeded on this question.But to reduce the time complexity i used vector.
@kcahdog thanks for the answer i will try to find a solution for higher values

You dont need to store all values upto 10^9. Just store the ones you come across in a map and reuse them.

Thats the best approach for it.

Still if you want to use dp you can store values upto 10^5 and compute for higher values.

My dp soln in C : link

Soln with Map(dictionary) in python : link

1 Like