Tìm thuật toán tìm tổng của các số không liền kề trong mảng

[toidihoc (Kim Khanh)]

Em có ý tưởng là lưu tất cả các tổng thỏa mãn vào 1 mảng rồi in ra phần tử max, nhưng chưa biết làm điều đó như thế nào.
Sau khi nháp 1 hồi, thì em mới chỉ “đếm” được số tổng thỏa mãn ứng với mỗi số n (n là kích thước mảng nguyên đã biết):
f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2) + 1, mọi n >= 3

Mọi người có cách nào triển khai ý tưởng trên, hoặc có ý tưởng giải quyết đơn giản nhẹ nhàng hơn thì giúp em phần thuật toán với ạ. (Phần xử lý tệp thì em tự làm được)

[rogp10]

Áp dụng QHĐ luôn, gọi S_i là tổng max các dãy con thỏa mãn, mà có phần tử cuối đứng trước phần tử thứ i (với S_1 = 0, S_2 = a_1, S_3 = \max(0, a_2)).