[Timus Online Judge] 1079. Maximum

Finally I got the AC.
I am so happy about this.
Step by Step to success.

According to this program.
It must consider about the time complex.

Time Limit: 2.0 second Memory Limit: 16 MB Consider the sequence of numbers ai, i = 0, 1, 2, …, which satisfies the following requirements: * a0 = 0 * a1 = 1 * a2i = ai * a2i+1 = ai + ai+1 for every i = 1, 2, 3, … . Write a program which for a given value of N (0 < N < 100000) finds the largest number among the numbers a0, a1, …, aN. Input Input contains not more than 10 lines containing one number N. The last line contains 0. Output For every N in the input write the corresponding maximum value found.

#include

int Maximum(int N){      

     if (N == 0)
        return 0;
     else if (N == 1)
        return 1;
     else if( (N % 2) == 0 )
        return Maximum(N/2)  ;
     else 
        return ( Maximum(N/2) + Maximum(N/2 + 1) );

}


int main(void){
 
    long i,num,max;
    long number[100001];

    for(i = 0 ; i <= 100000 ; i++){
         number[i]=Maximum(i);
    }

    while(scanf("%ld",&num)!=EOF){
       if (num==0) break;
       for(i=0,max=0;i<=num;i++)
            if(number[i]>max) max=number[i];
       printf("%ld\n",max);
    }      


return 0;
}