I decided to write post my solution and comment it, may be it will
be useful for someone.
So, you have recursively defined sequence. Of course first idea is
to write recursive function. But, we need to find max element from
1 to n and if you will call function for every n in order to find
maximum element, such algorithm will cost O(n^2). Another way is to
store results gotten before in special array and compare gotten result
with max of them.
I hope I helped you at least as it.
And here is accepted solution in C++:
#include <iostream>

#define max(a, b) ((a) < (b) ? (b): (a))

int last = 1;
int mem[100000];
int max[100000];

int F(int n)
{
    for (int i = last+1; i <= n; ++i) {
        if (i%2)
            mem[i] = mem[i/2]+mem[i/2+1];
        else
            mem[i] = mem[i/2];

        max[i] = max(mem[i], max[i-1]);
    }

    return max[n];
}

int main()
{
    mem[0] = 0; mem[1] = 1;
    max[0] = 0; max[1] = 1;

    int n;
    while (1) {
        std::cin >> n;

        if (!n) break;

        std::cout << F(n) << std::endl;
    }


    return 0;
}

well done, bro.... :)
here's another way... >>
--------------------------------------------------------------------------------------
#include <iostream>
using namespace std;

int arr[100000];

int find_max(int n)
{
    int maximum = 0;

    for(int i = 0; i <= n; i++)
        if(maximum < arr[i]) maximum = arr[i];

    return maximum;
}

int main()
{
    int n[11], i, idx;

    arr[0] = 0;
    arr[1] = 1;

    for(idx = 2; idx < 100000; idx++) {
        if(idx & 1) {       // when idx is odd.
            i = (idx-1) / 2;
            arr[idx] = arr[i] + arr[i+1];
        }
        else {              // when idx is even.
            i = idx / 2;
            arr[idx] = arr[i];
        }
    }

    i = 0;
    while(cin >> n[i], n[i++] != 0);

    i--;
    idx = i;

    for(i = 0; i < idx; i++) {
        cout << find_max(n[i]) << '\n';
    }

    return 0;
}
-------------------------------------------------------------------------------------

Edited by author 07.06.2015 08:42