find out such x that 2^x < n < 2^(x+1)
2^x means 2*2*...*2 x times

x=log(n)/log(2);//c++


the maximum value of a[i] i=1,2,...,2^x is
max=f(x);
where f(x) is the fibonacci sequence
f(0)=1 f(1)=1 f(n)=f(n-2)+f(n-1)

so i just have to look if there is a larger number from 2^x to n

it is easy to find out the value of a[i] without knowing a[1]...a[i-1]

if l=2*k and r=2*p
m=(l+r)/2
a[m]=a[l]+a[r];

it is rather easy to prove that
a[2^x]=1;
a[2^(x+1)]=1;

so you just have to do a binary search for i from 2^x to 2^(x+1) calculating the values for the left and right border

this is the function that does exactly that //c++
int b(long l,long r,long i,int v1,int v2)
{
long m=(l+r)/2;
if (i==m)    return (v1+v2);
if (i<m)    return j(l,m,i,v1,v1+v2);
        return j(m,r,i,v1+v2,v2);
}


I DON'T UNDERSTAND WHY, BUT WHEN I USE MATH.H I GET COMPILATION ERROR


good luck !!!

You have to use math instead of math.h ;-)

Manastireanu, thank you for your ideas, they pushed me to more deeply study the sequence.
A few comments:

> if l=2*k and r=2*p, m=(l+r)/2, a[m]=a[l]+a[r];

This is not true for all k and p, e.g., k=4 and p=7.   It is true starting with l=2^x and r = 2^(x+1),  m=(l+r)/2 and then recursing through more (l,r) with (l, m) and (m, r).

There are many interesting properties of this sequence, I encourage everyone to study it and to discover the patterns which will help solve this problem without "brute force", and will help with Maximum2