# Untitled

unknown

python

a year ago

2.0 kB

0

Indexable

Never

^{}

def L_Convex_S(A, left=0, mid=1, right=2, first_insert=True): """ A: given list left: left number mid: middle number right: right number first_insert: tracks if this is the first item being added to x. we add 3 numbers the first time, and then 1 after that that meets x's requirements """ # if right end goes past len(A) OR left is the same as middle index OR middle is the same as right index if right >= len(A) or left >= mid or mid >= right: return 0 #return 0 because we can't add any numbers to the sub-sequence x # iterate through all combinations of left, middle, and right numbers. Keep ignoring the eligibility for x ignore = max(L_Convex_S(A, left+1, mid, right, first_insert), L_Convex_S(A, left, mid+1, right, first_insert), L_Convex_S(A, left, mid, right+1, first_insert)) best = ignore # check eligibility for left, mid, nect to be part of x subsequence if A[left]+A[right] > 2*A[mid]: # if the first item being inserted if first_insert: # set first_insert to false first_insert = False # check for all remaining items to right (after we added left and mid to sub-seq) x = L_Convex_S(A, mid, right, right+1, first_insert) # since this is the first time we added a subsequence, increament by 3 include = 3 + x else: # check for all remaining items after right x = L_Convex_S(A, mid, right, right+1, first_insert) include = 1 + x # get the best from either ignoring or including this sub-seq if include > best: best = include return best print(L_Convex_S([1,2,3,14,5])) # 3 print(L_Convex_S([1,2,4,8,10,13])) # 5 print(L_Convex_S([1,3,2,2,4,1])) # 4 print(L_Convex_S([11,2,3,10])) # 4 print(L_Convex_S([11,2,3,7])) # 4 print(L_Convex_S([11,20,3])) # 0 print(L_Convex_S([3,2,2])) # 3 print(L_Convex_S([11,2,3,1,1,1,5,10])) # 6