Задача максимум

[Sanek_ntsk]

Не получается решить задачу http://acm.timus.ru/problem.aspx?space=1&num=1079

Моё решение

#include <iostream>
#include <fstream>
using namespace std;
const int MAX_N = 100000;
int main()
{
    int n, a[MAX_N], max;
    ifstream input("input.txt", ios::in);
    ofstream output("output.txt", ios::out);
    while (1) {
        input >> n;
        if (n == 0) break;
        for (int i = 0; i < MAX_N; i++) a[i] = 0;
        a[0] = 0; a[1] = 1;
        if (n > 1) {
            for (int i = 1; i < (n/2)+1; i++) {
                a[i*2] = a[i];
                a[(i*2)+1] = a[i] + a[i+1];
            }
        }
        max = a[n];
        for (int i = n; i > 1; i--)
            if (a[i] > max) max = a[i];
        output << max << endl;
    }
    input.close();
    output.close();
    
    return 0;
}

Дело в том, что моё решение даже первый тест не проходит, хотя пробовал и тот тест, который дан - работает, и те, что сам сделал - тоже работают. Что не так?

[Сtrl]

Отделили бы вы код получения элемента последовательности от нахождения максимума. Можно заключить в функцию:

int a(size_t i)
{
	if (i == 0)
		return 0;
	else if (i == 1)
		return 1;
	else if (i % 2 == 0)
		return a(i/2);
	else
		return a(i/2) + a(i/2+1);
}

Это достаточно простое решение, оно не требовательно к памяти, но работает очень долго. Неплохо бы, однажды вычислив значение, запомнить его, и не вычислять снова. Для этого создаем функтор:

class A_functor
{
public:
	int operator()(size_t i)
	{
		table.reserve(i);
		for (size_t j = table.size() - 1; j++ < i;)
		{
			if (j % 2 == 0)
				table.push_back(table[j/2]);
			else
				table.push_back(table[j/2] + table[j/2+1]);
		}
		return table[i];
	}
	A_functor()
	{
		table.push_back(0);
		table.push_back(1);
	}
private:
	vector<int> table;
} a;

Какой бы из способов вы ни выбрали, теперь вы сможете делать так:

cout << a(i); //на экран выведен i-ый элемент последовательности

Дальнейшее решение не должно составить труда.

[Sanek_ntsk]

Сtrl, спасибо за решение. Однако фишка заключалась в том, что вывод надо было делать в консоль, а не в файл. Я это исправил и все тесты прошли)