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^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;
    

    }



  • 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.




Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2