title: Java Calculate Max Steps of Stairs and skip stair
body: <p>I recently got an interview for an intern position and one of the questions was similar to this: </p>
  
  <blockquote>
    <p><strong>Input</strong>: n for number of actions, k for a stair that you could not step
    on</p>
    
    <p><strong>Question</strong>: Jack has n amount of actions where he wants to reach the
    maximum number of steps but cannot step on the kth stair. For each
    action, Jack can either stay at his current step or jump i steps if he
    is on his ith action and this keeps going until he finished his nth
    action.</p>
    
    <p><strong>Output</strong>: The maximum stair he can reach within n actions</p>
  </blockquote>
  
  <p>It was tested via Hackerrank (with the interviewer there) and I passed only 3 out of 8 test cases with the rest timing out</p>
  
  <p>This was my solution that was coded on the fly and I could not optimize it and was wondering if there was a much more optimized solution:</p>
  
  <pre><code>static int maxStep(int n, int k) {
      int result = 0;
      if (n == 0) {
          return result;
      } 
      return maxStepHelper(n,0, k, result);
  }
  
  static int maxStepHelper(int n,int i,int k,int result) {
      // At n+1 steps, previous steps' results are recorded and this is mainly used to stop and show previous results
      if (i == n+1) {
          return result;
      }
      int nextStep = i + result;
      if (nextStep == k) {
         return maxStepHelper(n,i+1,k,result);
      } 
      return Math.max(maxStepHelper(n,i+1,k,result),maxStepHelper(n,i+1,k,result+i));
  }
  </code></pre>
  
  <p>Note that I used a recursive approach which might not have helped</p>