How to go about a d-smooth sequence algorithm

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.

For example.. say seq[] = [2,4,8,3,1,12]

given that sequence, the algorithm should return "5" as d because you can add or subtract at most 5 to each element such that the function is strictly increasing.

I've tried several approaches and can't seem to get a solid technique down.

I've tried looping through the seq. and checking if seq[i] < seq[i+1]. If not, it checks if d>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].

I can't get it to be stable though and Its like I keep adding if statements that are more "special cases" for unique input sequences. People have suggested using a binary search approach, but I can't make sense of applying it to this problem.

Any tips and suggestions are greatly appreciated. Thanks!

Here's my code in progress - using Python - v4

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("fixes>>",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 >= left + 1
            nDelta = item2 - (item1 + 1)
            if(nDelta < 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("current nFix:",nFix)
    

    # Balance all fixes
    for i in range(len(aItems)):
        fixes[i] -= nFix

    print("final Fixes:",fixes)
    print("d:",nFix)
    print("original sequence:",seq[1:])
    print("result sequence:",aItems)

    return

Here's whats displayed:

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>> [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!

~Note~

I start at 1 rather than 0 due to the first element being a key

Solution

As anticipated, here is (or should be) the Python version of my initial solution:

def ComputeMaxDelta(aItems):
    # Create a copy to speed up comparison on modified values
    aItems = aItems[:]
    # Will store the fix values for every item
    # this should allocate 'length' times the 0 value
    fixes = [0] * len(aItems)

    # 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 >= left + 1
            nDelta = item2 - (item1 + 1)
            if(nDelta < 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 = (max(fixes)+1)/2 # corrected from **(max(s)+1)/2**

    # Balance all fixes
    for i in range(len(s)):
        fixes[i] -= nFix

    print("d:",nFix) # corrected from **print("d:",nDelta)**
    print("s:",fixes)

    return

I took your Python and fixed in order to operate exactly as my C# solution. I don't know Python, but looking for some reference on the web, I should have found the points where your porting was failing.

If you compare your python version with mine you should find the following differences:

You saved a reference aItems into s and used it as my fixes, but fixes was meant to start as all 0.
You didn't cloned aItems over itself, then every alteration to its items was reflected outside of the method.
Your for loop was starting at index 1, whereas mine started at 0 (the very first element).
After the check for nDelta you subtracted nDelta from both s and aItems, but as I stated at points 1 and 2 they were pointing to the same items.
The ceil instruction was unnedeed because the division between two integers produces an integer, as with C#.

Please remember that I fixed the Python code basing my knowledge only on online documentation, because I don't code in that language, so I'm not 100% sure about some syntax (my main doubt is about the fixes declaration).

Regards,
Daniele.