KAGAIN - Chiến trường Ô qua
Tác giả: khuc_tuan
Ngôn ngữ: Java
import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;
class MaxArmy {
public String getMax(int[] a) {
int[] l, r;
int n = a.length;
l=new int[n];
r=new int[n];
for(int i=0;i<n;++i) {
int x = i-1;
while( (x>=0) && (a[x]>=a[i]) ) x = l[x] ;
l[i] = x;
}
for(int i=n-1;i>=0;--i) {
int x = i+1;
while( (x<n) && (a[x]>=a[i]) ) x = r[x] ;
r[i] = x;
}
int max=-1, left=0, right=0;
for(int i=0;i<n;++i) {
int x = a[i]*(r[i]-l[i]-1);
if(x>max) {
max=x;
left = l[i] + 2;
right = r[i];
}
else if(x==max && left>l[i]+2) {
left = l[i] + 2;
right = r[i];
}
}
return Integer.toString(max) + " " + Integer.toString(left) + " " + Integer.toString(right);
}
}
public class Main{
public static void main(String[] Args) throws Exception {
BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
int tt = parseInt(kb.readLine());
for(int i=0;i<tt;++i) {
int n = parseInt(kb.readLine());
StringTokenizer st=new StringTokenizer(kb.readLine());
int[] a=new int[n];
for(int j=0;j<n;++j)
a[j] = parseInt(st.nextToken());
System.out.println( new MaxArmy().getMax(a) );
}
}
}