Example: Max Sum of Non Adjacent numbes - rFronteddu/general_wiki GitHub Wiki

You have to calculate the maximum sum of non adjacent numbers.

• we use two arrays
  • i keeps track of the maximum sum including the current element
  • e keeps track of the maximum sum excluding the last element

x= 4, 1, 1, 4, 2, 1

include = [4, 4, 5, 8, 8, 9] exclude = [0, 4, 4, 5, 8, 8]

nonAdj(x)
    n = x.len 
    in[0..n-1]
    ex[0..n-1]
    
    in[0] = x[0]
    ex[0] = 0

    for i = 1 to n-1
        i[i] = max(i[i-1], x[i] + e[i-1])
        e[i] = i[i-1]

    return i[n-1]