Algorithm to find the maximum amount of sub-acceptance

[rielyn]

I am committed to finding the maximum amount of subconsistency in the mass. I wrote a decision through the field, but it's too slow. How can he be optimized?

Purpose:

Number 1≤n≤10^2 stairs and whole numbers −10^4≤a[1],…,a[n]≤10^4the steps marked. Find the maximum amount that can be obtained by walking down the stairs (from zero to n-step) every time on one or two steps.

Sample Input 1:
2
1 2
Sample Output 1:
3
Sample Input 2:

2

2 -1

Sample Output 2:

1
Sample Input 3:

3

-1 2 1

Sample Output 3:

3

My decision through the C+++:

#include <iostream>

#include <climits>

#include <algorithm>

#define SZ 100
using namespace std;
int n, a[SZ + 1];
int foo(int step, int sum) {
int s1, s2;

if (step == n)
    s1 = s2 = sum;
else
    s1 = s2 = -INT_MAX;

if (step + 1 &lt;= n)
    s1 = foo(step + 1, sum + a[step + 1]);

if (step + 2 &lt;= n)
    s2 = foo(step + 2, sum + a[step + 2]);

return max(s1, s2);

}
int main(int argc, const char * argv[]) {
cin &gt;&gt; n;
for (int i = 1; i &lt;= n; i++) cin &gt;&gt; a[i];

cout &lt;&lt; foo(0, 0);

return 0;

}

[Bogopo]

On the positive steps, we should go in a row.
If there's one negative step, jump if two, jump on the one where it's smaller.
If the group of negative steps is more likely to include a lesson to minimize losses, and at least one jump through the step shall be required for each pair of consecutive steps.