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) );
		}
	}
}

Download