AtCoder-ABC189 C - Mandarin Orange【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

AtCoder Beginner Contest189は無念の1完でした…
ぽっきり心は折れましたが、心折れたまま頑張ってC問題を復習していきます！
AtCoder Beginner Contest 189 - AtCoder

AtCoder Beginner Contest189 C - Mandarin Orange

問題文

高橋君の前に N 枚の皿が一列に並べられており、左から i 番目の皿には Ai 個のみかんが置かれています。
高橋君は次の 3 つの条件を全て満たすような整数の組 (l,r,x) を 1 つ選びます。
・1≤l≤r≤N
・1≤x
・l 以上 r 以下の全ての整数 i について、x≤Ai
その後、高橋君は l 番目から r 番目まで (両端を含む) の全ての皿からみかんを x 個ずつ取って食べます。
整数の組 (l,r,x) を適切に選んだとき、高橋君は最大で何個のみかんを食べることができますか。

制約

・入力は全て整数
・1≤N≤10^4
・1≤Ai≤10^5

解答例

n = int(input())

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

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

解説

lからr番目の皿からx個のみかんを食べるとき最大で何個みかんを食べることができるか答える問題です。

lとrのすべての組み合わせを試す全探索で進めるとACできました。
各皿からみかんを食べる数のxは、lからrまでの範囲における皿のみかんの最小値です。
その最小値xと範囲にある皿の数をかけた値が、各範囲におけるみかんを食べられる最大値になります。
この値をans変数と比較して大きいほうをans変数に代入していきます。

ループを抜けた後にans変数を出力すればACでした。

NG例

n = int(input())

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

ans = 0
for l in range(n):
    for r in range(l+1,n):
        if r-l == 1:
            num = A[l]
        else:
            Aa = A[l:r]
            num = min(Aa) * (r - l + 1)
        if num > ans:
            ans = num            
else:
    print(ans)