## 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())
n = int(f_in.readline())
v_s = f_in.readline().rstrip('\n').split()
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:
lines = fp.readlines()
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)