# [SOLVED] More efficient way to handle big lists in python?

## Issue

I’m writing a python script to solve this exercise:

Given in input a vector V of N integers we want to find, for each size between 1 and N, the maximum
of the minimumâ€™s of every contiguous subsequence in the vector.

The script I wrote works fine with N<1000 but when I try it with greater values, it just keeps running without ending. I guessed it’s too slow because of the 3 for-loops and the many .append() to big lists, but how can I solve that? Or am I wrong and there is another problem I don’t see?

``````f_name = input("Inserire nome del file: ")

f_in = open("inputs/"+f_name, "r")
f_out = open("outputs/"+f_name, "w")

# n = int(input())

v = [int(i) for i in v_s]

maxs = []

for size in range(1, n+1):
mins = []
for i in range(n):
subseq = []
if (i+size <= n):
for j in range(size):
subseq.append(v[i+j])
if (len(subseq) > 0):
mins.append(min(subseq))
maxs.append(max(mins))

for max in maxs:
f_out.write(str(max) + " ")

f_in.close()
f_out.close()
``````

Here are some examples of input and output.

## Solution

Algorithm from GeeksforGeeks (with some readability improvements):

``````def fill(array, auxiliary, my_range):
s = []
for i in my_range:
while s and array[s[-1]] >= array[i]:
s.pop()

if s:
auxiliary[i] = s[-1]
s.append(i)

def solution(array, n, left, right):
ans = [0] * (n + 1)
for i in range(n):
my_len = right[i] - left[i] - 1
ans[my_len] = max(ans[my_len], array[i])

for i in range(n - 1, 0, -1):
ans[i] = max(ans[i], ans[i + 1])
return ans[1:]

def main(filename):

with open("{}/{}".format("input", filename), "r") as fp:

n = int(lines[0])
v = [int(s.strip()) for s in lines[-1].split()]

left = [-1] * (n + 1)
right = [n] * (n + 1)

fill(v, left, range(n))
fill(v, right, range(n-1, -1, -1))
result = solution(v, n, left, right)
result = [str(res) for res in result]

output = " ".join(result)
with open("{}/{}".format("output", filename), "w") as fp:
fp.write(output)
print(output)

if __name__ == '__main__':
f_name = input("Inserire nome del file: ")
main(f_name)
``````

Answered By – Marco Valle

Answer Checked By – Willingham (BugsFixing Volunteer)