Maximieren Sie den rechteckigen Bereich unter Histogramm

Question

Ich habe ein Histogramm mit ganzzahligen Höhen und konstanter Breite 1. Ich möchte die rechteckige Fläche unter einem Histogramm maximieren. z.B.:

 _
| |
| |_ 
|   |
|   |_
|     |

Die Antwort auf diese Frage wäre 6, 3 * 2, unter Verwendung von col1 und col2.

O(n^2) brute force ist mir klar, ich möchte einen O(n log n) Algorithmus. Ich versuche, dynamisches Programmieren im Sinne eines O(n log n)-Algorithmus mit maximal ansteigender Teilfolge zu verstehen, aber ich komme nicht weiter. Sollte ich einen Divide-and-Conquer-Algorithmus verwenden?

PS: Personen, die über ein ausreichendes Ansehen verfügen, werden gebeten, die Markierung "Teile und herrsche" zu entfernen, wenn es keine solche Lösung gibt.

Nach den Kommentaren von mho: Ich meine die Fläche des größten Rechtecks, das vollständig hineinpasst. (Danke j_random_hacker für die Klarstellung :) ).

Answer 1

python-3

    a=[3,4,7,4,6]
    a.sort()
    r=0
    for i in range(len(a)):
        if a[i]* (n-1) > r:
            r = a[i]*(n-i)
    print(r)

Ausgabe:

16

Answer 2

Sie können die O(n)-Methode verwenden, bei der die maximale Fläche unter dem Histogramm mit Hilfe von Stack berechnet wird.

long long histogramArea(vector<int> &histo){
   stack<int> s;
   long long maxArea=0;
   long long area= 0;
   int i =0;
   for (i = 0; i < histo.size();) {
    if(s.empty() || histo[s.top()] <= histo[i]){
        s.push(i++);
    }
    else{
        int top = s.top(); s.pop();
        area= histo[top]* (s.empty()?i:i-s.top()-1);
        if(area >maxArea)
            maxArea= area;
    }
  }
  while(!s.empty()){
    int top = s.top();s.pop();
    area= histo[top]* (s.empty()?i:i-s.top()-1);
    if(area >maxArea)
        maxArea= area;
 }
 return maxArea;
}

Zur Erklärung können Sie hier lesen http://www.geeksforgeeks.org/largest-rectangle-under-histogram/