fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class HISTOGRA {
  5.     public static void main(String[] args) {
  6.         try {
  7.             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  8.             StringBuilder sb = new StringBuilder();
  9.             while (true) {
  10.                 StringTokenizer st = new StringTokenizer(br.readLine());
  11.                 int N = Integer.parseInt(st.nextToken());
  12.                 if (N == 0)
  13.                     break;
  14.                 int max_area = 0;
  15.                 int cur_area = 0;
  16.                 int arr[] = new int[N + 1];
  17.                 Stack<Integer> stack = new Stack<Integer>();
  18.  
  19.                 for (int i = 0; i < N; i++) {
  20.                     arr[i] = Integer.parseInt(st.nextToken());
  21.                 }
  22.                 arr[N] = 0;
  23.  
  24.                 int i = 0;
  25.                 for (i = 0; i <= N; i++) {
  26.                     if (stack.isEmpty()) {
  27.                         stack.push(i);
  28.                     } else if (arr[i] >= arr[stack.peek()]) {
  29.                         stack.push(i);
  30.                         i++;
  31.                     }
  32.                     if (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
  33.                         while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
  34.                             int index = stack.pop();
  35.                             if (stack.isEmpty()) {
  36.                                 cur_area = arr[index] * i;
  37.                                 max_area = cur_area > max_area ? cur_area : max_area;
  38.                             } else {
  39.                                 cur_area = arr[index] * (i - stack.peek() - 1);
  40.                                 max_area = cur_area > max_area ? cur_area : max_area;
  41.                             }
  42.                         }
  43.                         stack.push(i);
  44.                     }
  45.                 }
  46.                 sb.append(max_area + "\n");
  47.  
  48.             }
  49.             System.out.print(sb);
  50.         } catch (Exception e) {
  51.  
  52.         }
  53.     }
  54.  
  55. }
  56.  
Success #stdin #stdout 0.06s 32464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dKrEOa
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!