Algorithm to find the maximum amount of sub-acceptance
-
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^4
the 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:
1Sample 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 <= n) s1 = foo(step + 1, sum + a[step + 1]); if (step + 2 <= n) s2 = foo(step + 2, sum + a[step + 2]); return max(s1, s2);
}
int main(int argc, const char * argv[]) {
cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; cout << foo(0, 0); return 0;
}
-
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.