2025 CSCI2100E Lab Session #2

Time limit: 5000ms
Memory limit: 256mb

Description:

You are tasked with implementing a function that finds the maximum rectangle area that can be formed using the histogram.
A histogram is represented by an array of integers where each integer represents the height of a bar.
Given the histogram heights, the function should return the area of the largest rectangle that can be formed by using any number of contiguous bars.
You are required to complete the following function:

int largestRectangleArea(int* heights, int heightsSize)
- heights: An integer array of size heightsSize representing the heights of the bars in the histogram.
- heightSize: The number of bars in the histogram (i.e., the length of the heights array).


You can refer page 3-6 in Stacks slides for the implementation of a stack. We have implemented it here in the template.


Sample Input 1:
4
4 2 3 4

Sample Output 1:
Enter the number of bars in the histogram:
Enter the heights of the bars:
The largest rectangle area is: 8

Explanation:
The largest rectangle is formed by the first bars up to the last bar with height 2, giving an area of 8 (4*2)

Sample Input 2:
5
1 2 3 4 5

Sample Output 2:
Enter the number of bars in the histogram:
Enter the heights of the bars:
The largest rectangle area is: 9

Explanation:
The largest rectangle is formed by the third bars up to the last bar with height 3, giving an area of 9 (3*3)

Sample Input 3:
3
1 1 1

Sample Output 3:
Enter the number of bars in the histogram:
Enter the heights of the bars:
The largest rectangle area is: 3

Explanation:
The largest rectangle is formed by the all the bars, giving an area of 3 (3*1)

Sample Input 4:
1
8

Sample Output 4:
Enter the number of bars in the histogram:
Enter the heights of the bars:
The largest rectangle area is: 8

Explanation:
The largest rectangle is formed by the only one bars, giving an area of 8 (1*8)

-------------------------Copy the following code, complete it and submit-------------------------



/*
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SEQ_LEN 30
#define MAX_NUM_SEQ 100

typedef enum{FALSE = 0, TRUE = 1} Boolean;

typedef struct{
    int size;
    int top;
    int *stacklist;
} Stack;

Stack *createStack(int size){
    Stack *s;
    s = (Stack*)malloc(sizeof(Stack));
    s->size =size;
    s->stacklist = (int*)malloc(size * sizeof(int));
    s->top = -1;
    return s;
}

Boolean isFull(Stack *s){
    if (s->top == s->size -1)
        return TRUE;
    else return FALSE;
}

Boolean isEmpty(Stack *s){
    if (s->top == -1)
        return TRUE;
    else return FALSE;
}

void push(Stack *s, int e){
    if (!isFull(s)){
        s->top++;
        s->stacklist[s->top] = e;
    }
}

int pop(Stack *s){
    int i;
    if (!isEmpty(s)){
        i = s-> stacklist[s->top];
        s->top--;
        return i;
    }else{printf("error\n"); return -1;}
}

int top(Stack *s){ return s->stacklist[s->top];}


int largestRectangleArea(int* heights, int heightsSize) {
    Stack* stack = createStack();
    int maxArea = 0;
    int i = 0;

    while (i < heightsSize) {
        // code here

        }
    }

    while (stack->top != -1) {
        // code here
    }

    free(stack->stacklist);
    free(stack);
    return maxArea;
}



int main() {
    int n;
    printf("Enter the number of bars in the histogram: ");
    scanf("%d", &n);

    int* heights = (int*)malloc(n * sizeof(int));

    printf("Enter the heights of the bars:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &heights[i]);
    }

    int result = largestRectangleArea(heights, n);
    printf("The largest rectangle area is: %d\n", result);

    free(heights);
    return 0;
}

-------------------------------------------End of Code-------------------------------------------