Data Structure and Algorithm Design II

Sections

• Dynamic Programming

• Max Sum Subarray Problem

Dynamic Programming

Outline

• Overview

• Applications

• Benefit and Challenges

• Complexity

Overview

• An algorithmic paradigm

• Break into overlapping subproblems

• Only calculate once to avoid repeated work

• Store the result in a table for future use

Characteristics

• Optimal substructure

• Overlapping subproblems

• Memoization/tabulation

• Recursive formulation

• Either top-down or bottom-up

DP Algorithms

• Enumeration, decision or optimization types of problems

• Fibonacci numbers

• Knapsack problem

• Longest common subsequence

• Integer partition

• Coin change

• Rod cutting

• Matrix chain multiplication

Quick Exercises:

• Can you categorize the above problems by their problem types?

• Why dynamic programming is not a good fit for bin packing problems?

Benefit and Challenges

Complexity Analysis

Max Sum Subarray

• Given an array of integers, find the contiguous subarray with the largest sum. The array can contain both negative and positive values.

• For array \([-2, -3, 4, -1, -2, 1, 5, -3]\), the contiguous subarray with the largest sum is \([4, -1, -2, 1, 5]\) with sum 7.

• Many real-life applications

  • Stock market

  • Image processing

  • Bioinformatics

• Problem type: Optimization

• Need exact solution

• Satisfies

  • Optimal substructure

  • Overlapping subproblems

• Solutions

  • Brute-force \(\Theta(n^2)\)

  • Divide and conquer \(\Theta(n \log n)\)

  • Dynamic Programming (Kadane’s algorithm) \(\Theta(n)\)

Brute-force Solutions

• Consider all possible subarrays and compute their sums

function brute_force_max_subarray(arr):
  max_sum = -infinity

  for start from 0 to length(arr) - 1:
    sum_of_subarray = 0

    for end from start to length(arr) - 1:
      sum_of_subarray = sum_of_subarray + arr[end]

      if sum_of_subarray > max_sum:
        max_sum = sum_of_subarray

  return max_sum

Divide and Conquer Solution

• Divide the array into two halves

• Recursively find the maximum subarray sum in:

  • Left half

  • Right half

  • Crossing the midpoint

function max_subarray(arr, low, high):
  if low == high:
    return arr[low]

  mid = (low + high) / 2
  return max(max_subarray(arr, low, mid),
            max_subarray(arr, mid + 1, high),
            max_crossing_sum(arr, low, mid, high))

Divide and Conquer Solution (cont.)

function max_crossing_sum(arr, low, mid, high):
  left_sum = -infinity
  sum = 0
  for i from mid downto low:
    sum = sum + arr[i]
    if sum > left_sum:
        left_sum = sum

  right_sum = -infinity
  sum = 0
  for j from mid + 1 to high:
    sum = sum + arr[j]
    if sum > right_sum:
        right_sum = sum

  return left_sum + right_sum

Dynamic Programming Solution

• Kadane’s algorithm

• Idea: Compute the maximum subarray sum ending at each position

• At each end position, the maximum subarray sum is either:

  • The maximum subarray sum ending at the previous position plus the current element

  • The current element

• Scan the array from left to right only once

Dynamic Programming Solution (cont.)

Consider the array \([-2, 1, -3, 4, -1, 2, 1, -5, 4]\):

• Start with \(current\_max = arr[0] = -2\) and \(global\_max = -2\).

• At the second element (1), \(current\_max\) is \(max(-2+1, 1)\), which is 1. \(global\_max\) is now \(max(-2, 1)\), which is 1.

• This process continues, updating \(current\_max\) and \(global\_max\) with each new element.

• By the end of the array, \(global\_max\) contains the maximum sum, which in this case is 6 from the subarray \([4, -1, 2, 1]\).

Dynamic Programming Solution (cont.)

function kadane_algorithm(arr):
  current_max = global_max = arr[0]

  for index from 1 to length(arr) - 1:
    current_max = max(arr[index], current_max + arr[index])

    global_max = max(global_max, current_max)

  return global_max