Largest Rectangular Area in Histogram






Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. 

For simplicity, assume that all bars have same width and the width is 1 unit.

SAMPLE INPUT: 
7 
{6, 2, 5, 4, 5, 1, 6} 

 SAMPLE OUTPUT: 
12

 CODE

Comments

Post a Comment

Popular posts from this blog

C library function - qsort()

Image
Description               The C library function void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)) sorts an array. Parameters base -- This is the pointer to the first element of the array to be sorted. nitems -- This is the number of elements in the array pointed by base. size -- This is the size in bytes of each element in the array. compar -- This is the function that compares two elements. Return Value This function does not return any value Code   #include <stdio.h> #include <stdlib.h> int values [] = { 88 , 56 , 100 , 2 , 25 }; int cmpfunc ( const void * a , const void * b ) { return ( *( int *) a - *( int *) b ); } int main () { int n ; printf ( "Before sorting the list is: \n" ); for ( n = 0 ; n < 5 ; n ++ ) { printf ( "%d " , values [ n ]); } qsort (...
Read more

Solution For LRU Stack

The objective is to i mplement a stack using LinkedList. You need to implement push and pop function. When push is called, insert the items in list at the head. When the stack is empty and pop is called return 0 The maximum stack size allowed is 5 Whenever a push is called Case 1 : Value is NOT present in stack: If the stack is full (has 5 items) then remove the oldest pushed item on the stack and push the new item. If the stack is not full, then push the new item Case 2 : Value is already present in stack: Since the item is already present in the stack move it to the top of the stack. Algorithm Step 1 :- Create a class(or structure ,depends on the programming language) with a data members for the creation of linked list. Step 2:- Implement push and pop function using a linked list as we do normally. Step 3:- In push function before pushing the element to stack check the size of the stack. ->if size is less than 5 ,then push the element normally. ->els...
Read more

Find The Ring (PUZZLE)

There is a new magician in town. His trick is known as "Find the Ring". He puts 3 glasses at 3 spots on the table, labeling them as 0, 1 and 2. Now, he hides a ring under one of the glasses. The glasses are opaque and placed upside down, so that the ring is not visible to the audience. Now, he begins to make certain swaps in between adjacent glasses, i.e. the glass at position 0 can be swapped with that at position 1, and the glass at position 2 can be swapped with glass at 1. Assuming that all swaps are done randomly with equal probability of 50%, you have to find index of the glass that is most likely to have the ring, at the end. In case of a tie, choose the one with lower index. Assume that the glass containing the ring was swapped exactly N times. Input: First line contain two space separated integers, index and N. index is index of glass that initially contains the ring and N is the total number of swaps involving the glass with ring. SAMPLE INPUT   3  1 1 0 1 2 ...
Read more