Problem: Let us consider an array with real values (positive and negative) Determine a subarray containing elements with alternating signs (positive followed negative, negative followed by positive) for which the sum of the absolute value of the elements is maximal.
After running the code with this list it doesn’t give me the right output
the output is [6, -3, 7, -5, 13, 12, 8, -9] but it should be [6, -3, 7, -5, 13, -9, 8]
a_list = [2, 6, -3, 7, -2, -5, 10, 13, 13, 13, 13, 12, 12, 12, 12, 12, 8, 8, 8, 8, 8, 8, -9, 8, -9, -9, -9, -9, -9, -9, -9, -9, 12, 12, 12, 12, 12] # [6, -3, 7, -5, 12]
sum_list = []
i=0
while i <len(a_list)-1:
if (a_list[i] < 0 and a_list[i+1] > 0):
if a_list[i] in sum_list:
pass
else:
if sum_list[-1]<0:
pass
else:
sum_list.append(a_list[i])
if (a_list[i] > 0 and a_list[i+1] < 0):
if a_list[i] in sum_list:
pass
else:
if sum_list[-1]>0:
pass
else:
sum_list.append(a_list[i])
else:
if a_list[i]>0 and a_list[i+1]>0:
if max(a_list[i],a_list[i+1]) in sum_list:
pass
else:
sum_list.append(max(a_list[i],a_list[i+1]))
if a_list[i]<0 and a_list[i+1]<0:
if min(a_list[i],a_list[i+1]) in sum_list:
pass
else:
sum_list.append(min(a_list[i], a_list[i + 1]))
i=i+1
print(sum_list)```
Advertisement
Answer
Update: the code is not correct in general, I’m at it …
Update: corrected version see below
This gives the expected result (with a few inline comments):
#https://stackoverflow.com/questions/65673470/
# test lists for a few edge cases
list_1 = []
list_2 = [0]
list_3 = [0, 0]
list_4 = [0, 0, 0]
list_5 = [-2, 4, -2, 4]
list_6 = [2, -4, 2, -4]
t_list = [ 2, 6
, -3
, 7
, -2, -5
, 10, 13, 13, 13, 13, 12, 12, 12, 12, 12, 8, 8, 8, 8, 8, 8
, -9
, 8
, -9, -9, -9, -9, -9, -9, -9, -9
, 12, 12, 12, 12, 12
] # expected result: [6, -3, 7, -5, 13, -9, 8]
all_lists = [list_1, list_2, list_3, list_4, list_5, list_6, t_list]
def sign_differs(n1, n2):
'''return True if n1 and n2 have different signs.'''
return n1 < 0 and n2 >= 0 or n1 >= 0 and n2 < 0
for a_list in all_lists:
print(f'a_list: {a_list}')
sum_list = []
prev_idx = 0
for idx in range(1, len(a_list)):
n1, n2 = a_list[idx-1], a_list[idx]
if n1 in sum_list:
continue
if sign_differs(n1, n2): # +/- or -/+ detected
if a_list[prev_idx] >= 0:
max_abs = max(a_list[prev_idx:idx]) # largest positive
else:
max_abs = min(a_list[prev_idx:idx]) # smallest negative
if not max_abs in sum_list:
sum_list.append(max_abs)
prev_idx = idx
print(f'sum_list: {sum_list}n')
Output including a few test cases:
a_list: [] sum_list: [] a_list: [0] sum_list: [] a_list: [0, 0] sum_list: [] a_list: [0, 0, 0] sum_list: [] a_list: [-2, 4, -2, 4] sum_list: [-2, 4] a_list: [2, -4, 2, -4] sum_list: [2, -4] a_list: [2, 6, -3, 7, -2, -5, 10, 13, 13, 13, 13, 12, 12, 12, 12, 12, 8, 8, 8, 8, 8, 8, -9, 8, -9, -9, -9, -9, -9, -9, -9, -9, 12, 12, 12, 12, 12] sum_list: [6, -3, 7, -5, 13, -9, 8]
Corrected version:
#https://stackoverflow.com/questions/65673470/
# test lists for a few (edge) cases
list_1 = []
list_2 = [0]
list_3 = [0, 0]
list_4 = [0, 0, 0]
list_5 = [-2, 4, -2, 4]
list_6 = [2, -1, 2, -2, -3, -4, 3]
list_7 = [-99, 2, -1, 3, -1, 4, 5, -3, -3, 4, -1, -3, -4, -5, 2, 3, -5, 6, 4, 7]
t_list = [ 2, 6
, -3
, 7
, -2, -5
, 10, 13, 13, 13, 12, 12, 12, 8, 8, 8
, -9
, 8
, -9, -9, -9
, 12, 12, 12
] # expexted result: [6, -3, 7, -5, 13, -9, 8]
all_lists = [list_1, list_2, list_3, list_4, list_5, list_6, list_7, t_list]
def alternating_nums(a_list):
sum_list = []
if not a_list:
return sum_list
number = a_list[0]
sum_list = [number]
srch_neg = number >= 0 # look for next pos./neg. number
other_ok = True
for number in a_list:
if srch_neg: # searching for a neg. number
if number >= 0:
if number in sum_list:
continue
if number <= sum_list[-1]:
continue
if not other_ok:
continue
sum_list[-1] = number # found a "better" one
continue
if number < 0:
if number in sum_list:
other_ok = False
continue
sum_list.append(number)
srch_neg = False # now searching for a pos. number
other_ok = True # a consecutive smaller neg. will be ok, too
continue
else: # searching for a pos. number
if number < 0:
if number in sum_list:
continue
if number >= sum_list[-1]:
continue
if not other_ok:
continue
sum_list[-1] = number # found a "better" one
continue
if number >= 0:
if number in sum_list:
other_ok = False
continue
sum_list.append(number)
srch_neg = True # now searching for a neg. number
other_ok = True # a consecutive larger pos. will be ok, too
continue
return sum_list
for a_list in all_lists:
print(a_list)
sum_list = alternating_nums(a_list)
print(sum_list, 'n')