ABC 189 C問題

C - Mandarin Orange

要約

(l, r, x)の組を決めるには，(l, r)の組み合わせが決まればその範囲の中の最小値をxにすればうまく行くと考え，(l, r)を決める全探索はO(N^2)で回るのでうまくいくと思っていた．

N = int(input())
A = list(map(int, input().split()))
ans = 0
for l in range(N+1):
   for r in range(l, N+1):
       s = A[l:r]
       if len(s) != 0:
           x = min(s)
           val = x * len(s)
           ans = max(ans, val)

print(ans)

しかし，このやり方だとTLEになる．

その理由は，二重for文の中の

s = A[l:r]

にある．python(PyPy)ではリストの中から一つの要素を取り出すのはO(1)だが，リストの中から複数の要素を取り出そうとしたら最悪O(N)になる．

そのため，このやり方だとO(N^3)で回ってしまいTLEとなる．

解決策

最初のやり方は，

・範囲を決める→最小値を決定する→計算

の順だったがそうではなくて，

・最小値を更新する　→　次の要素とどっちが小さいか比較する　→　小さい方の要素×範囲で値を更新する

という流れになる．イメージ的には

最初のやり方は図の上のようにfor文で範囲を決めていたが解決策では，図の下のように，for文で見る要素をずらしていくイメージで解いていく．

N = int(input())
A = list(map(int, input().split()))

ans = 0
for l in range(N):
   val = A[l]
   for r in range(l, N):
       val = min(val, A[r])
       ans = max(ans, val * (r-l+1))
print(ans)