\(l,r\) の組を全探索することを考えます。\(l,r\) を固定したとき、\(x\) は大きな値にする方が良いので、\(x=\min(A_l,\ldots,A_r)\) とするのが最適です。したがって、区間最小値が計算できればよいです。

セグメントツリーなどを用いて \(O(N^2 \log N)\) で求めることも出来ますがTLEになります。

「まず \(l\) を固定し、\(r\) を順に大きくしながら \(x\) を更新する」という方法により \(O(N^2)\) で求めることができます。

実装例(C++)

#include<bits/stdc++.h>
using namespace std;

int a[10010];
int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++)cin >> a[i];

	int ans=0;
	for(int l=0;l<n;l++){
		int x=a[l];
		for(int r=l;r<n;r++){
			x=min(x,a[r]);
			ans=max(ans,x*(r-l+1));
		}
	}
	cout << ans;
}

また、セグメントツリーではなく、sparse table などのデータ構造を用いて区間 \(\min\)を \(O(1)\) で求めることでも、\(O(N^2)\) でこの問題を解くことが出来ます。

なおこの問題は \(O(N)\) で解く事も出来ます。