1#include <stdio.h>
2#include <stdlib.h>
3
4// Simple deque implementation
5typedef struct Deque {
6    int front, rear, size;
7    unsigned capacity;
8    int* array;
9} Deque;
10
11Deque* createDeque(unsigned capacity) {
12    Deque* deque = (Deque*)malloc(sizeof(Deque));
13    deque->capacity = capacity;
14    deque->front = deque->size = 0;
15    deque->rear = capacity - 1;  // End of the queue
16    deque->array = (int*)malloc(deque->capacity * sizeof(int));
17    return deque;
18}
19
20int isFull(Deque* deque) { return (deque->size == deque->capacity); }
21int isEmpty(Deque* deque) { return (deque->size == 0); }
22void pushBack(Deque* deque, int item) {
23    if (isFull(deque)) return;
24    deque->rear = (deque->rear + 1) % deque->capacity;
25    deque->array[deque->rear] = item;
26    deque->size = deque->size + 1;
27}
28
29void popFront(Deque* deque) {
30    if (isEmpty(deque)) return;
31    deque->front = (deque->front + 1) % deque->capacity;
32    deque->size = deque->size - 1;
33}
34
35int front(Deque* deque) {
36    if (isEmpty(deque)) return -1;
37    return deque->array[deque->front];
38}
39
40int back(Deque* deque) {
41    if (isEmpty(deque)) return -1;
42    return deque->array[deque->rear];
43}
44
45void popBack(Deque* deque) {
46    if (isEmpty(deque)) return;
47    deque->rear = (deque->rear - 1 + deque->capacity) % deque->capacity;
48    deque->size = deque->size - 1;
49}
50
51int maxResult(int* nums, int numsSize, int k) {
52    Deque* dq = createDeque(numsSize);
53    pushBack(dq, 0);
54    for (int i = 1; i < numsSize; i++) {
55        if (front(dq) < i - k) {
56            popFront(dq);
57        }
58        nums[i] += nums[front(dq)];
59        while (!isEmpty(dq) && nums[i] >= nums[back(dq)]) {
60            popBack(dq);
61        }
62        pushBack(dq, i);
63    }
64    int maxScore = nums[numsSize - 1];
65    free(dq->array);
66    free(dq);
67    return maxScore;
68}

1