主页 / 问题 / 1530196
Accepted
Настя
Asked:2023-07-12 18:03:54 +0000 UTC2023-07-12 18:03:54 +0000 UTC

代码未通过时间限制（python优化）

  • 772

我解决了这个问题：

给定n 个整数a 1 , a 2 , …, a n。

查找1 ≤ l <的所有整数对 ( l , r)上的最大值max(a l , a l+1 , … , a r ) min(a l , a l+1 , …, a r ) r≤n。

输入数据

第一行包含一个整数t ( 1 ≤ t ≤ 10000 ) — 测试用例的数量。

每个测试用例的第一行包含一个整数 n ( 2 ≤ n ≤ 10 5 )。

每个测试用例的第二行包含n 个整数 a 1 , a 2 , …, a n ( 1 ≤ a i ≤ 10 6 )。

保证所有测试用例的n之和不超过3·10 5。

输出

对于每个测试用例，打印一个整数——条件下乘积的最大可能值。

例子

输入数据

4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328

输出

12
6
4761
381274500335

我为它写了代码：

n=int(input()) 
for x in range(n):
    m=int(input()) 
    a=list(map(int, input().split())) 
    ans=a[0]*a[1] 
    for l in range(m-1):
        for r in range(l+1, m):
            s=a[l:r+1] 
            if min(s)*max(s)>ans:
                ans=min(s)*max(s)
    print(ans)

但没有超过时间限制，请告诉我如何加速！

python

1 个回答

  1. Best Answer

    考虑线段(l, r)上的乘积：

        *
  *           *
*       *
      *     *
          *
---------------
l . m . . . . r

    令m为该段中最大值的位置。如果m < r ，则考虑线段(m, m + 1)，否则考虑线段(m - 1, m) 。为了确定性，设为(m, m + 1)。

    (l, r)和(m, m + 1)的最大值相同。(m, m+1)的最小值大于或等于(l, r)的最小值。因此， (m, m + 1)的乘积不小于(l, r) 的乘积。

    也就是说，对于任何长段（l，r），都会呈现具有相同或更大乘积的短段（m，m + 1） 。不必考虑长线段，将在长度为二的线段上获得最大乘积。

    此类段的数量是线性的，这意味着程序的复杂度也将是线性的。现在你的程序的复杂度是立方的。对于n = 10 5您的程序将执行大约10 15次操作。线性程序将执行大约10 5。加速10 10倍。

    for _ in range(int(input())):
    input() # skip n
    a = tuple(map(int, input().split())) 
    print(max(max(al, ar) * min(al, ar) for al, ar in zip(a, a[1:])))

    $ cat input.txt
4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328

$ python max-min.py < input.txt
12
6
4761
381274500335
    • 3

相关问题