Envío 6293

Código

import java.util.HashMap;
import java.util.Objects;
import java.util.Scanner;

public class Main {
    private static final HashMap<Integer, Integer> memoization = new HashMap<Integer, Integer>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

        int max = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int h = findMinHeight(i, j, array);
                int b = j - i + 1;
                int area = h * b;

                if (area > max) {
                    max = area;
                }
            }
        }

        System.out.println(max);
    }

    private static int findMinHeight(int start, int end, int[] array) {
        int key = new Key(start, end).hashCode();
        if (memoization.containsKey(key)) {
            memoization.get(key);
        }

        if (start == end) {
            memoization.put(key, array[start]);
            return array[start];
        }

        int value = array[start];
        int recResponse = findMinHeight(start+1, end, array);

        int min = Math.min(value, recResponse);
        memoization.put(key, min);
        return min;
    }

    private static class Key {
        private final int start;
        private final int end;

        public Key(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int hashCode() {
            return Objects.hash(start, end);
        }
    }
}