he-009

# HumanEval/9

Implement a file **`solution.py`** that completes the function below. Keep the given name and signature; your file must define it at module level.

```python
from typing import List, Tuple


def rolling_max(numbers: List[int]) -> List[int]:
    """ From a given list of integers, generate a list of rolling maximum element found until given moment
    in the sequence.
    >>> rolling_max([1, 2, 3, 2, 3, 4, 2])
    [1, 2, 3, 3, 3, 4, 4]
    """
```

<!-- imported from OpenAI HumanEval (HumanEval/9) -->

# Auto-generated from OpenAI HumanEval HumanEval/9. Do not edit by hand.
from solution import *  # noqa: F401,F403 (prompt helpers may be referenced by tests)
from solution import rolling_max as candidate

METADATA = {
    'author': 'jt',
    'dataset': 'test'
}


def check(candidate):
    assert candidate([]) == []
    assert candidate([1, 2, 3, 4]) == [1, 2, 3, 4]
    assert candidate([4, 3, 2, 1]) == [4, 4, 4, 4]
    assert candidate([3, 2, 3, 100, 3]) == [3, 3, 3, 100, 100]


def test_he_009():
    check(candidate)

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```python
from typing import List, Tuple


def rolling_max(numbers: List[int]) -> List[int]:
    """ From a given list of integers, generate a list of rolling maximum element found until given moment
    in the sequence.
    >>> rolling_max([1, 2, 3, 2, 3, 4, 2])
    [1, 2, 3, 3, 3, 4, 4]
    """
    result = []
    current_max = float('-inf')
    for num in numbers:
        if num > current_max:
            current_max = num
        result.append(current_max)
    return result
```

The task is to implement a function `rolling_max` that takes a list of integers and returns a list where each element is the maximum value found from the beginning of the list up to that position.

Looking at the example:
- Input: `[1, 2, 3, 2, 3, 4, 2]`
- Output: `[1, 2, 3, 3, 3, 4, 4]`

Let me trace through:
- Position 0: max([1]) = 1
- Position 1: max([1, 2]) = 2
- Position 2: max([1, 2, 3]) = 3
- Position 3: max([1, 2, 3, 2]) = 3
- Position 4: max([1, 2, 3, 2, 3]) = 3
- Position 5: max([1, 2, 3, 2, 3, 4]) = 4
- Position 6: max([1, 2, 3, 2, 3, 4, 2]) = 4

So for each position i, I need to return the maximum of numbers[0:i+1].

The simplest approach is to iterate through the list, keeping track of the current maximum, and append it to the result list.

```python
def rolling_max(numbers: List[int]) -> List[int]:
    result = []
    current_max = float('-inf')
    for num in numbers:
        if num > current_max:
            current_max = num
        result.append(current_max)
    return result
```

This is O(n) time complexity and O(n) space complexity for the result.

Let me verify with the example:
- Start: current_max = -inf
- num = 1: 1 > -inf, current_max = 1, result = [1]
- num = 2: 2 > 1, current_max = 2, result = [1, 2]


- num = 3: 3 > 2, current_max = 3, result = [1, 2, 3]
- num = 2: 2 > 3? No, current_max = 3, result = [1, 2, 3, 3]
- num = 3: 3 > 3? No, current_max = 3, result = [1, 2, 3, 3, 3]
- num = 4: 4 > 3, current_max = 4, result = [1, 2, 3, 3, 3, 4]
- num = 2: 2 > 4? No, current_max = 4, result = [1, 2, 3, 3, 3, 4, 4]

The algorithm correctly maintains the running maximum at each step, matching the expected output.