python - 在给定范围内查找列表的所有可能子列表的高效和 Pythonic 方法，以及将其中的所有元素相乘后的最小乘积？

Question

我已经实现了这两件事。

1. 在给定范围 (i ,j) 中找到列表的所有可能子列表。
   

   A = [ 44, 55, 66, 77, 88, 99, 11, 22, 33 ] 
   Let, i = 2 and j = 4
   

   然后，给定范围 (2,4) 中列表 "A" 的可能子列表是:
   

   [66], [66,77], [66,77,88], [77], [77,88], [88]
   

2. 并且，将子列表的所有元素相乘后的结果乘积的最小值:
   
   因此，将上述子列表中的所有元素相乘后的结果列表将变为

   X = [66, 5082, 447216, 77, 6776, 88]`    
   

   现在，上面列表的最小值，即 min(X) 即 66

我的代码:

i, j = 2, 4
A = [ 44, 55, 66, 77, 88, 99, 11, 22, 33 ] 
O, P = i, i
mini = A[O]
while O <= j and P <= j:
    if O == P:
        mini = min(mini, reduce(lambda x, y: x * y, [A[O]]))
    else:
        mini = min(mini, reduce(lambda x, y: x * y, A[O:P + 1]))
    P += 1
    if P > j:
        O += 1
        P = O
print(mini)

我的问题:

对于更大的列表和更大的范围，这段代码需要更多的时间来执行!
是否有任何可能的“Pythonic”方式来降低上述代码的时间复杂度？

提前致谢!

编辑:

明白了。但是，如果有多个这样的可能子列表具有相同的最小产品，

1. 我需要最长的子列表范围 (i,j)
   
2. 如果还有多个子列表具有相同的“最长子范围”，我需要打印具有最低起始索引的子间隔。

考虑这个列表 A = [2, 22, 10, 12, 2] 如果 (i,j) = (0,4)。
有一条领带。 Min product = 2 有两种可能性 '(0,0)' 和 '(4,4)' 。
两个子列表范围 = 0 [ (0-0) 和 (4-4) ]
在这种情况下，我需要 print (minproduct, [sublist-range]) = 2, [0,0]

尝试使用字典，它适用于某些输入但不适用于所有输入!如何“有效地”做到这一点？
谢谢!

Answer 1

首先，给定列表和索引范围，我们可以得到子列表A[i : j + 1]

[66, 77, 88]

对于正整数a和b，a * b不小于a或 b。所以你不需要做乘法，两个或多个元素相乘不可能有更小的结果。此列表的最小值是所有相乘结果的最小值。

所以结果是:

min(A[i : j + 1])