Find subsequence with the maximum sum

[1, -2, 3, 5, 7] => [3,5,7]
[4, -2, 5] => [5]
[5, -6, 1, 2, 3, 4] => [1,2,3,4]

Solution:

def max_sum_subseq(arr):
    max_sum = 0
    max_start_index = 0
    max_length = 0
    current_sum = 0
    current_start_index = 0
    
    for i in range (0,len(arr)):
        if current_sum == 0 and arr[i] > 0:
             current_start_index = i
             
        current_sum += arr[i]
        if current_sum <= 0:
              current_sum = 0
              continue
       
        if current_sum >= max_sum:
            max_sum = current_sum
            max_length = i - current_start_index + 1
            max_start_index = current_start_index

Find longest ascending series (not same as upsequence problem)

Given a sequence of distinct integers, remove as few elements as possible so that the remaining sequence appears sorted in ascending order.

Example:

1 2 3 8 10 5 6 7 12 9 11 4 0
1 2 3      5 6 7    9 11

Brute force solution:

def arrangements(k,arr):
        if len(arr) == 1:
                return [arr]
        if k == 1:
                return [ [i] for i in arr ]
        else:
                L=[]
                for i in arr:
                        iarr = arr[:]
                        iarr.remove(i)
                        for v in arrangement (k-1,iarr):
                                L.append ( [i] + v )
                return L

def is_ascending(arr):
        res = True
        for i in range(0,len(arr)-1):
                if arr[i] > arr[i+1]:
                        res = False
                        break
        return res

def longest_ascending(arr):
        max_arg = None
        max_size = 0
        for k in range (1,len(arr)):
                argts = arrangements (k,arr)
                for a in argts:
                        if is_ascending(a) and len(a) > max_size:
                                max_size = len(a)
                                max_arg = a

        return max_arg

Printing all possible combinations of brackets

Write a function Brackets(int n) that prints all combinations of well-formed brackets. For Brackets(3) the output would be

((())) (()()) (())() ()(()) ()()()

def brackets(n):
        if n == 2:
                return ["()"]
        else:
                L = []
                for b in brackets(n-2):
                        L.append( "(" + b + ")" )
                        L.append( "()" + b )
                        if not b.find ( "((" ):
                                L.append( b + "()" )
                return L

print brackets(2)
print brackets(6)

Print all possible variations of a password

An iterative version that has been implemented and tested:

def variations(str, char_variations):
        result = []
        for i in range(0,len(str)):
                tmp_result = []
                c = str[i]
                vars = char_variations.get(c)
                if vars is None:
                        vars = []
                vars = vars + [c]

                if len(result) > 0:
                        for partial_r in result:
                                for v in vars:
                                        tmp_result.append(partial_r + v)
                else:
                        for v in vars:
                                tmp_result.append(v)

                result = tmp_result

        return result


char_variations = { 'a': ['0','o'] , 'l': ['1' , 'I'] }

print variations ('allo' , char_variations)

An here is a recursive version that has been implemented and tested

def variations(str,char_variations):
        if len(str) == 0:
                return []

        c = str[0]
        vars = char_variations.get(c)

        if len(str) == 1:
             if vars:
                  return vars
             else:
                  return [c]

        if vars is None:
                vars = []
        vars = vars + [c]
        

        subL = variations (str, char_variations)
        L = []

        for l in subL:
                 for v in vars:
                        L += [ v + l ]
        
        return L

char_variations = { 'a': ['0','o'] , 'l': ['1' , 'I'] }

print map ( str , variations (list ('allo') , char_variations) )

Binary search and array rotation

The following solution has been implemented and verified:

def binsearch(arr, val, start, end):
    if start == end and arr[start] <> val:
       return -1
    index = (end+start)/2
    if val == arr[index]:
       return index
    elif val < arr[index]:
       return binsearch(arr, val, start , index)
    elif val > arr[index]:
       return binsearch(arr, val, index , end)

arr = range(1,8)
print arr
print binsearch ( arr , 3, 0, len(arr) )
print binsearch ( arr , 7, 0, len(arr) )

Additionnal question:
The array was rotated. How would search in it?

Answer, find the index of max value, iMax and in the previous function, replace

    index = (end+start)/2

by

    index = (iMax + (end+start)/2) % len(arr)

Print out all combinations of k numbers out of 1...N

e.g. when k = 2, n = 4
Print out 12, 13, 14, 23, 24, 34

def combi (k,arr):
        if k == 1:
                return [[i] for i in arr]
        elif k == 0 or len(arr) == 0:
                return []

        L = []
        for i in range (0,len(arr)):
                arr2 = arr[:]
                arr2.remove(arr[i])
                for v in  combi (k-1 , arr2):
                        L.append( [arr[i]] + v )

        return L

print combi ( 2 , range(1,4) ) 
 

One limitation with this function is that it returns 14 but also 41
The following code solves this problem

def combi2 (k,arr):
        if k == 1:
                return [[i] for i in arr]
        elif k == 0 or len(arr) == 0:
                return []

        L = []
        arr2 = arr[:]
        while len(arr2) > 0:
                val = arr2.pop(0)

                for v in  combi (k-1 , arr2):
                        L.append( [val] + v )

        return L