daily pastebin goal
18%
SHARE
TWEET

Untitled

a guest Aug 12th, 2017 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. unsigned long int *createArray(int);
  4. void histogra();
  5. int main()
  6. {
  7.     histogra();
  8.     return 0;
  9. }
  10.  
  11.  
  12. unsigned long int * createArray(int n)
  13. {
  14.     return (unsigned long int *)malloc(n*sizeof(unsigned long int));
  15. }
  16.  
  17. void histogra()
  18. {
  19.     int tos = -1, top, n = 0, i;
  20.     unsigned long long int maxArea = -1, area = 0;
  21.     while (1)
  22.     {
  23.         scanf("%d", &n);
  24.         if (n < 1)
  25.             return;
  26.         maxArea = 0;
  27.         area = 0;
  28.         tos = -1;
  29.         unsigned long int *arr = createArray(n);
  30.         unsigned long  int *stack = createArray(n);
  31.  
  32.         for (i = 0; i < n; i++)
  33.         {
  34.             scanf("%ld", &arr[i]);
  35.             if (tos == -1)
  36.             {
  37.                 stack[++tos] = i;
  38.                 continue;
  39.             }
  40.             if (arr[i] >= arr[stack[tos]])
  41.             {
  42.                 stack[++tos] = i;
  43.                 continue;
  44.             }
  45.             while (tos != -1){
  46.                 if (arr[i] < arr[stack[tos]])
  47.                 {
  48.                     top = stack[tos--];
  49.                     if (tos == -1)
  50.                         area = arr[top] * i;
  51.                     else
  52.                         area = arr[top] * (i - stack[tos] - 1);
  53.                     if (area > maxArea)
  54.                         maxArea = area;
  55.                 }
  56.                 else
  57.                     break;
  58.             }
  59.             stack[++tos] = i;
  60.         }
  61.         while (tos != -1)
  62.         {
  63.             top = stack[tos--];
  64.             if (tos == -1)
  65.                 area = arr[top] * i;
  66.             else
  67.                 area = arr[top] * (i - stack[tos] - 1);
  68.             if (area > maxArea)
  69.                 maxArea = area;
  70.         }
  71.         free(arr);
  72.         free(stack);
  73.  
  74.         printf("%lld\n", maxArea);
  75.     }
  76. }
RAW Paste Data
Top