Again it’s been a while after previous post…

O(nlogn) – Sort
Sort the list, and retrieve the nth one.

O(n*k) – Partial Sort
There can be multiple ways to do partial sort, one of them being selective sort: loop the list – first cycle get the biggest one; second cycle get the second one etc. till the Kth cycle. On each cycle we can move the number to the front, so that l[0:K] is sorted after Kth cycle.

O(n*logk) – Binary Search
This can be a little bit tricky but the idea is like binary search – divide and conquer:

def findKth(l, left, right, k):
    pivot_pos = partition(l, left, right)
    la = pivot_pos - left + 1
    lb = right - pivot_pos
    if la > k:
        return findKth(l, left, pivot_pos, k)
    else:
        return findKth(l, pivot_pos + 1, right, k - la)

O(n*logk) – Use a data structure to track K numbers
The idea is: use a data structure to store first K numbers. Initially, put first K numbers in L to the data structure; then loop through the list: for each element, check if the min number of the data structure is less than it, if not then pass, else remove the min number in the datastructure, and put the number in. Apparently min heap is a valid data structure to do it. O(n*logk)

O(n) – bitvec
Again make use of bitvec if possible….

Algorithm 1 – O(n^2): enumerate all possible subarray
This is pretty straightforward, but second program improves the performance by not repeating calculating sum.

def max_subarray_enum(l):
    """
    >>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_enum(l))
    95
    >>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_enum(l))
    32
    """
    length = len(l)
    def sum(i, len):
        # assertion
        val = 0
        for n in range(0, len):
            val += l[i + n]
        return val
    # loop invariant:
    # l[i:i+len] is subarray which we need to calculate the sum
    # termination: enumerated all possible i j combinations
    max_val = l[0]
    for i in range(0, length):
        for subarray_len in range(1, length - i + 1):
            val = sum(i, subarray_len)
            if val > max_val: max_val = val
    return max_val

def max_subarray_enum2(l):
    """
    >>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_enum2(l))
    95
    >>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_enum2(l))
    32
    """
    length = len(l)
    # loop invariant:
    # l[i:i+len] is subarray which we need to calculate the sum
    # termination: enumerated all possible i j combinations
    max_val = l[0]
    for i in range(0, length):
        val = 0
        for subarray_len in range(1, length - i + 1):
            val += l[i + subarray_len - 1]
            if val > max_val: max_val = val
    return max_val

Algorithm 2 – O(nlogn): divide and conquer

def max_subarray_divide(l, left, right):
    """
    >>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_divide(l, 0, len(l) - 1))
    95
    >>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_divide(l, 0, len(l) - 1))
    32
    """
    # divide and conquer:
    # max = max_val(
    #   recur(firsthalf),
    #   recur(secondhalf),
    #   max_sum_left + max_sum_right
    # )
    def max_val(vals):
        # TODO: assert
        max = vals[0]
        for val in vals:
            if max < val: max = val
        return max
    def max_sum(start, end, step):
        if step > 0 and start > end:
            return 0
        elif step < 0 and end > start:
            return 0
        index_range = range(start, end + step, step)
        max = l[index_range[0]]
        sum = max
        for i in index_range[1:]:
            sum += l[i]
            if max < sum: max = sum
        return max

    if left > right:
        return 0  # actually, this one should be minus infinity
    if left == right:
        return l[left]

    mid = left + ((right - left) >> 1)
    # NOTE for the following statement, if we put max_sum(mid, right, 1)
    # then there will be dead recursive loop
    max_sum_right = max_sum(mid + 1, right, 1)
    max_sum_left = max_sum(mid, left, -1)
    max_sum_first = max_subarray_divide(l, left, mid)
    max_sum_right = max_subarray_divide(l, mid + 1, right)

    return max_val([max_sum_first, max_sum_right, max_sum_left + max_sum_right])

Algorithm 3 – O(n) with O(n) space: dynamic programming

def max_subarray(l):
    """
    >>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray(l))
    95
    >>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray(l))
    32
    """
    # following are the dynamic programming vars:
    # - tail_max[n] means max subarray that ends at position n
    # - max[n] means max subarray in array l[0:n+1]
    #
    # following are the dynamic programming equations:
    # - tail_max[n] = max(tail_max[n-1]+l[n], l[n])
    # - max[n] = max(max[n-1], tail_max[n])
    #
    def max_val(a, b):
        return a if a > b else b
    # init data structures
    length = len(l)
    max = [None] * length
    tail_max = [None] * length
    # initial values
    if len(l) == 0:
        return 0
    max[0] = l[0]
    tail_max[0] = l[0]
    # dynamic programming: loop
    for n in range(1, length):
        tail_max[n] = max_val(tail_max[n-1]+l[n], l[n])
        max[n] = max_val(max[n-1], tail_max[n])
    return max[n]

Algorithm 4 – O(n) with O(1) space: dynamic programming with improvement

def max_subarray_o1space(l):
    """
    >>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_o1space(l))
    95
    >>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
    >>> print(max_subarray_o1space(l))
    32
    """
    def max_val(a, b):
        return a if a > b else b
    # initial values
    if len(l) == 0:
        return 0
    max_prev = l[0]
    tail_max_prev = l[0]
    # init data structures
    max = max_prev
    tail_max = tail_max_prev
    # dynamic programming: loop
    for n in range(1, len(l)):
        tail_max = max_val(tail_max_prev+l[n], l[n])
        max = max_val(max_prev, tail_max)
        tail_max_prev = tail_max
        max_prev = max
    return max

2D array?…
OK, I’ll ignore the code here….but it can be converted to 1D array like:

for upper_bound in range(0, first_dim_length(matrix)):
  for lower_bound in range(upper_bound, first_dim_length(matrix):
    merge the 2D array in within upper and lower bound to 1D array
    use dynamic programming approach to solve it

For a while I’ve been reading programming pearls…Then I wanted some change so picked up the beauty of programming (again). This time it went pretty smooth, due to the fact that’s the second time I read it – although the first time I didn’t really look into all the details…Anyway I want to blog about two dynamic programming problems:

Problem: Discount
Note:
this is a simplified version from the book…

Problem:
suppose you need to buy N books. The price is $p / book, and if you order several books together in an order you will get corresponding discount as following:
1 book – d1
2 books – d2
3 books – d3
4 books – d4
5 books – d5
Please compute the minimum money you have to spend.

Solution:
- Let f(n) to be the minimum money to buy n books.
- f(n) = min(
f(n-1) + p*d1,
f(n-2) + 2*p*d2,
f(n-3) + 3*p*d3,
f(n-4) + 4*p*d4,
f(n-5) + 5*p*d5
)
- The initial values (or the termination conditions if you see it as recursive…) are first 5 items.

Problem: Backpack
The official name should be ’0-1 knacksack problem’ if I googled it correctly…The problem is suppose you have a bag that can afford weight w, and you got n items that values are v[i] and weight are w[i], calculate the maximum value you can put in your bag.

Solution:
The key here is to identify the variables for dynamic programming. So if we look at this problem as f(n, w) where n means n items and w means the weight capacity is w, then the model is obvious:
f(n, w) = max(
f(n-1, w), // if we don’t put the nth item in the bag
f(n-1, w – w[n-1]) + v[n-1] // if we put the nth item in the bag
)