Instead of changing an algorithm to fit a problem, a better approach is to modify the problem so that it fits an existing algorithm.
Modelling a problem is sometimes the hardest part of solving it.

FIT2004 Sample Question

In 2026 S1 offering, the final exam of FIT2004 covers 35% of overall marks.

The exam is split into three parts, where the last part has 6 questions.

Students need to choose 3 questions to answer, and each answered question will hold 5 marks towards the final result.

The last question of the 26S1 D/HD test, as I recalled, is about fireworks:

Firework Observation

There are several fireworks that are in the shape of quadratic function, we name them:

fw1, fw2, …., fwn.

We take photos of the firework every 1 second, assuming the time is:

t0, t1, …, tm.

For each firework at every recorded time, two values are given:

The height of the firework at that moment;
The brightness of the firework, which may be either positive or negative.

For example, at time tj, firework fwi has:

height: hij
brightness: bij

Sample Picture

sample picture

The picture is generated using AI according to my memory, not the actual picture on the exam paper.

We want the continuous height interval:

that produces the maximum total brightness.

In addition, give the time complexity in terms of:

the number of seconds recorded
the number of fireworks

My Solution

The first key point is to ignore the quadratic function shape of the fireworks.

Instead, we abstract the graph into data:

For each firework, we know its height and brightness at each time step.

The key step is to model the question into a scenario that is solvable using a known algorithm.

Modeling the Question

Each recorded firework observation can be represented as a pair:

where:

is the height of the firework at the recorded time;
is the brightness at that height.

Multiple observations may occur at the same height.

We first combine the brightness of all observations at a certain height.

Define:

as the total brightness of all fireworks observed at height .

Therefore:

In other words:

For every height , we add the brightness values of all recorded points whose height equals .

The problem is then transformed into:

Given sorted heights:

with corresponding accumulated brightness:

find a continuous height interval:

that maximizes:

Solving the Modeled Question

Let’s ignore the height first.

Given an array of numbers, either negative or positive, how do we find the continuous interval where the sum is the maximum?

This is exactly the Maximum Subarray problem in Leetcode Hot100.

We could use the simple 1D dynamic programming approach to solve it.

The Dynamic Programming

We define the minimal subproblem as:

where:

is the maximum sum of a continuous interval that ends exactly at height ;
is the starting height of that interval.

For the next height , we have two choices.

Case 1: Start a new interval

If:

then extending the previous interval would reduce the total sum.

Therefore:

Case 2: Extend the previous interval

Otherwise, if:

we extend the interval ending at :

Therefore, the recurrence relation is:

or:

The base case is:

While calculating the DP states, we record the index with the largest value of:

Since represents an interval ending at , the optimal height interval is:

The maximum accumulated brightness is:

The Time Complexity

Let:

be the number of fireworks;
be the number of recorded time steps;
be the number of distinct heights among all recorded observations.

Each firework produces one observation at every recorded time step.

Therefore, the total number of observations is:

First, we iterate through every observation and combine the brightness values recorded at the same height.

Using a map, this takes:

Next, we sort the distinct heights.

(Ignore if the height is already sorted.)

This takes:

Finally, we apply the 1D DP:

Therefore, the total time complexity is:

Since the number of distinct heights cannot exceed the total number of observations:

the worst-case time complexity is:

Disclaimer

The question may square with the actual question, but the general idea is the same.

There are total of 6 questions of the same difficulty, but I only have time to finish this question only.

Judging from my final score of the unit, my formatting of the answer is very poor :(, so I posted this revised answer.

This answer may not be optimal.