[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())
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)