code-jam.py

Maximum jump from reach end
    for i in range(1, n):
        jumps[i] = float('inf')
        for j in range(i):
            if (i <= j + arr[j]) and (jumps[j] != float('inf')):
                jumps[i] = min(jumps[i], jumps[j] + 1)
                break
    return jumps[n-1]

Coins minimum count problem
    for i in range(1, V + 1):
         
        # Go through all coins smaller than i
        for j in range(m):
            if (coins[j] <= i):
                sub_res = table[i - coins[j]]
                if (sub_res != sys.maxsize and
                    sub_res + 1 < table[i]):
                    table[i] = sub_res + 1


Shortest common subsequence
    for i in range(0, m + 1):
        for j in range(0, n + 1):
             
            # Below steps follow above recurrence
            if not i:
                dp[i][j] = j;
            else if not j:
                dp[i][j] = i;
            else if (a[i - 1] == b[j - 1]):
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],
                                   dp[i][j - 1]);


Longest common substring
def lcs(X, Y, m, n, dp):
 
    if (m == 0 or n == 0):
        return 0
 
    if (dp[m][n] != -1):
        return dp[m][n]
 
    if X[m - 1] == Y[n - 1]:
        dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp)
        return dp[m][n]
 
    dp[m][n] = max(lcs(X, Y, m, n - 1, dp),lcs(X, Y, m - 1, n, dp))
    return dp[m][n]
 


Longest increasing pattern
    for i in range(1, N):
        for j in range(i):
            if (arr[i] >= arr[j] and lis[i] < lis[j] + 1):
                lis[i] = lis[j] + 1




maximum-difference-zeros-ones-binary-string/
def findlength(arr, s="11000010001", n=length(s), ind, st,     dp = [[-1] * 3 ]):
     
    # If string is over
    if ind >= n:
        return 0
 
    # If the state is already calculated.
    if dp[ind][st] != -1:
        return dp[ind][st]
 
    if not st:
        dp[ind][st] = max(arr[ind] +
           findlength(arr, s, n, ind + 1, 1, dp),
            (findlength(arr, s, n, ind + 1, 0, dp)))
    else:
        dp[ind][st] = max(arr[ind] +
         findlength(arr, s, n, ind + 1, 1, dp), 0)
          
    return dp[ind][st]



def findLength(string, n):
    current_sum = 0
    max_sum = 0
 
    # traverse a binary string from left
    # to right
    for i in range(n):
 
        # add current value to the current_sum
        # according to the Character
        # if it's '0' add 1 else -1
        current_sum += (1 if string[i] == '0' else -1)
 
        if current_sum < 0:
            current_sum = 0
 
        # update maximum sum
        max_sum = max(current_sum, max_sum)
 
    # return -1 if string does not contain
    # any zero that means all ones
    # otherwise max_sum
    return max_sum if max_sum else 0

Maximum wine 

if (dp[begin][end] != -1):
        return dp[begin][end]
 
    year = n - (end - begin)
 
    if (begin == end):
        return year * price[begin]
 
    # x = maximum profit on selling the
    # wine from the front this year
    x = price[begin] * year + \
        maxProfitUtil(price, begin + 1, end, n)
 
    # y = maximum profit on selling the
    # wine from the end this year
    y = price[end] * year + \
        maxProfitUtil(price, begin, end - 1, n)
 
    ans = max(x, y)
    dp[begin][end] = ans


Minimum number of jumps to reach end
 # value to jumps[i]
    for i in range(1, n):
        jumps[i] = float('inf')
        for j in range(i):
            if (i <= j + arr[j]) and (jumps[j] != float('inf')):
                jumps[i] = min(jumps[i], jumps[j] + 1)
                break
    return jumps[n-1]

Max subarray
def max_subarray(numbers):
    """Find the largest sm of any contiguous subarray."""
    best_sum = 0
    current_sum = 0
    for x in numbers:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum