array of size 10^9 problem

[ankur12106037]

question-->http://www.spoj.com/problems/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;
std::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;}
}

[BasV]

Vectors still use arrays internally. Maybe you can divide your vector into multiple vectors, and use a
std::vector<std::vector<long>>
instead?

Or: if speed is not important, use a std::list.

[Mats]

Have you considered that this problem doesn't even need an array and that there are far easier solutions?

[ankur12106037]

@Mats I solved this problem without using array.But when i submitted the solution i got time limit exceeded.This happended because many of the subproblems are overlaping and get calculted again and again.Like there are many common factors of 2 & 4 or 2&3 which will be calculated many times.So overcome this i used the technique called memoization by this i stored the values already computed reducing the time complexity.That's why i used arrays or vectors

[ankur12106037]

@BasV using multiple vectors will be very tideous .I will try using list.
What is the difference list will create..it will allow me to enter input upto 10^9?

[coder777]

Note this:

Memory limit: 256MB

You can cache only a part of the whole range.

Do not use vector. It dynamically increases it's memory (if capacity is exhausted). Means that it keeps the old values in memory, allocating the extended memory, copy.

[BasV]

A vector stores its data as one big array in memory, while a list allocates a bit of memory for each element. So, vectors are way faster to access members, but lists don't need one big strip of memory.

[Disch]

Mats wrote:

Have you considered that this problem doesn't even need an array and that there are far easier solutions?

+100 @ Mats

You are on the wrong line of thought here. Creating a building a ginormous array is going to exceed the memory requirements for the program, and is also going to be make your program a mess and overly complicated for such a simple problem


EDIT:

Are you familiar with std::map? It might be worth looking into for this...


EDIT AGAIN:

I tried submitting my own solution but I keep getting "wrong output". Wtf. My output isn't wrong unless I'm misunderstanding the problems... and there's no way to debug since it won't tell me the input and expected output.

FINAL EDIT:

And I can't use auto? Screw this. =P

[ankur12106037]

@ Disch thanks,map helped me getting the right solution.Vector was taking the space also for those values which might not be calculated in the solution.