title: How to go about a d-smooth sequence algorithm
body: <p>I'm really struggling to design an algorithm to find d, which is the lowest value that can be added or subtracted (at most) to make a given sequence strictly increasing.</p>
  <p>For example.. say seq[] = [2,4,8,3,1,12]</p>
  <p>given that sequence, the algorithm should return &quot;5&quot; as d because you can add or subtract at most 5 to each element such that the function is strictly increasing.</p>
  <p>I've tried several approaches and can't seem to get a solid technique down.</p>
  <p>I've tried looping through the seq. and checking if seq[i] &lt; seq[i+1]. If not, it checks if d&gt;0.. if it is, try to add/subtract it from seq[i+1]. Otherwise it calculates d by taking the difference of seq[i-1] - seq[i].</p>
  <p>I can't get it to be stable though and Its like I keep adding if statements that are more &quot;special cases&quot; for unique input sequences. People have suggested using a binary search approach, but I can't make sense of applying it to this problem.</p>
  <p>Any tips and suggestions are greatly appreciated. Thanks!</p>
  <hr />
  <h2>Here's my code in progress - using Python - v4</h2>
  <pre><code>def ComputeMaxDelta3(seq):
      # Create a copy to speed up comparison on modified values
      aItems = seq[1:] #copies sequence elements from 1 (ignores seq[0])
      # Will store the fix values for every item
      # this should allocate 'length' times the 0 value
      fixes = [0] * len(aItems)
      print(&quot;fixes&gt;&gt;&quot;,fixes)
  
      # Loop until no more fixes get applied
      bNeedFix = True
      while(bNeedFix):
          # Hope will have no fix this turn
          bNeedFix = False
  
          # loop all subsequent item pairs (i should run from 0 to length - 2)
          for i in range(0,len(aItems)-1):
              # Left item
              item1 = aItems[i]
              # right item
              item2 = aItems[i+1]
  
              # Compute delta between left and right item
              # We remember that (right &gt;= left + 1
              nDelta = item2 - (item1 + 1)
              if(nDelta &lt; 0):
                  # Fix the right item
                  fixes[i+1] -= nDelta
                  aItems[i+1] -= nDelta
                  # Need another loop
                  bNeedFix = True
  
      # Compute the fix size (rounded up)
      # max(s) should be int and the division should produce an int
      nFix = int((max(fixes)+1)/2)
      print(&quot;current nFix:&quot;,nFix)
      
  
      # Balance all fixes
      for i in range(len(aItems)):
          fixes[i] -= nFix
  
      print(&quot;final Fixes:&quot;,fixes)
      print(&quot;d:&quot;,nFix)
      print(&quot;original sequence:&quot;,seq[1:])
      print(&quot;result sequence:&quot;,aItems)
  
      return
  </code></pre>
  <hr />
  <h2>Here's whats displayed:</h2>
  <pre><code>Working with: [6, 2, 4, 8, 3, 1, 12] 
      [0]= 6 So the following numbers are the sequence: 
           aItems = [2, 4, 8, 3, 1, 12] 
  
  fixes&gt;&gt; [0, 0, 0, 0, 0, 0]
  current nFix: 6
  final Fixes: [-6, -6, -6, 0, 3, -6]
  d: 1
  original sequence: [2, 4, 8, 3, 1, 12]
  result sequence: [2, 4, 8, 9, 10, 12]
  
  d SHOULD be: 5
  
  done!
  </code></pre>
  <h2>~Note~</h2>
  <p>I start at 1 rather than 0 due to the first element being a key</p>