Consider searching for all pairs \(l, r\). When \(l, r\) is fixed, the larger \(x\) is the better, so \(x=\min(A_l,\ldots,A_r)\) is optimal. Therefore, we want to find the minimum value of a segment.

One can find it in a total of \(O(N^2 \log N)\) time with a segment tree, but it will lead to TLE.

Instead, one can use the method where “first fix \(l\), then update \(x\) while increasing \(r\) one by one” to find them in a total of \(O(N^2)\) time.

Sample Code (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;
}

Also, one can solve this problem in a total of \(O(N^2)\) with certain data structure, not like segment tree, but like sparse table, in order to find segment \(\min\) in \(O(1)\) time each.

Also, this problem can be solved in a total of \(O(N)\) time.